fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct aho_corasick
  4. {
  5.     struct node
  6.     {
  7.         int suf_link=-1,exit_link=-1;
  8.         int nxt[128];
  9.         vector<int> leaf;
  10.         node()
  11.         {
  12.             fill(nxt,nxt+128,-1);
  13.         }
  14.     };
  15.     vector<node> g={node()};
  16.     void add_string(string s,int sidx)
  17.     {
  18.         int p=0;
  19.         for(char c:s){
  20.             if(g[p].nxt[c]==-1){
  21.                 g[p].nxt[c]=g.size();
  22.                 g.emplace_back();
  23.             }
  24.             p=g[p].nxt[c];
  25.         }
  26.         g[p].leaf.push_back(sidx);
  27.     }
  28.     void build_automaton()
  29.     {
  30.         for(deque<int> q={0};q.size();q.pop_front()){
  31.             int v=q.front(),suf_link=g[v].suf_link;
  32.             if(v!=0){
  33.                 if(g[suf_link].leaf.size()) g[v].exit_link=suf_link;
  34.                 else g[v].exit_link=g[suf_link].exit_link;
  35.             }
  36.             for(int i=0;i<128;i++){
  37.                 int &nxt=g[v].nxt[i];
  38.                 int nxt_sf;
  39.                 if(v!=0) nxt_sf=g[suf_link].nxt[i];
  40.                 else nxt_sf=0;
  41.                 if(nxt==-1) nxt=nxt_sf;
  42.                 else{
  43.                     g[nxt].suf_link=nxt_sf;
  44.                     q.push_back(nxt);
  45.                 }
  46.             }
  47.         }
  48.     }
  49.     vector<int> get_sidx(int p)
  50.     {
  51.         vector<int> a;
  52.         for(int v=g[p].leaf.size()?p:g[p].exit_link;v!=-1;v=g[v].exit_link){
  53.             for(int j:g[v].leaf){
  54.                 a.push_back(j);
  55.             }
  56.         }
  57.         return a;
  58.     }
  59. };
  60. int main()
  61. {
  62.     ios_base::sync_with_stdio(false);
  63.     cin.tie(0);
  64.     cout.tie(0);
  65.     string e;
  66.     while(getline(cin,e)){
  67.         int n=stoi(e);
  68.         vector<int> s_size(n);
  69.         aho_corasick ac;
  70.         for(int a=0;a<n;a++){
  71.             string s;
  72.             getline(cin,s);
  73.             ac.add_string(s,a);
  74.             s_size[a]=s.size();
  75.         }
  76.         ac.build_automaton();
  77.         vector<int> ans[n];
  78.         string t;
  79.         getline(cin,t);
  80.         int p=0;
  81.         for(int i=0;i<t.size();i++){
  82.             p=ac.g[p].nxt[t[i]];
  83.             for(int j:ac.get_sidx(p)){
  84.                 ans[j].push_back(i-s_size[j]+1);
  85.             }
  86.         }
  87.         for(vector<int> v:ans){
  88.             if(!v.size()) cout<<"\n";
  89.             else{
  90.                 for(int i:v){
  91.                     cout<<i<<" ";
  92.                 }
  93.                 cout<<"\n";
  94.             }
  95.         }
  96.     }
  97. }
  98.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
2
p
pup
Popup
2
You
peek a boo
you speek a bootiful language
4
anas
ana
an
a
bananananaspaj
stdout
copy 
2 4 
2 

5 
7 
1 3 5 7 
1 3 5 7 
1 3 5 7 9 12
https://ideone.com/rqKdNb
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!