fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct Aho {
  4.     struct Node {
  5.         map<char,int> nxt;
  6.         int link=0;
  7.         vector<int> out;
  8.     };
  9.     vector<Node> t;
  10.     Aho(){ t.emplace_back(); }
  11.     void add(const string &s,int id){
  12.         int v=0;
  13.         for(char c:s){
  14.             if(!t[v].nxt.count(c)){
  15.                 t[v].nxt[c]=t.size();
  16.                 t.emplace_back();
  17.             }
  18.             v=t[v].nxt[c];
  19.         }
  20.         t[v].out.push_back(id);
  21.     }
  22.     void build(){
  23.         queue<int> q;
  24.         for(auto &p:t[0].nxt){
  25.             t[p.second].link=0;
  26.             q.push(p.second);
  27.         }
  28.         while(!q.empty()){
  29.             int v=q.front();q.pop();
  30.             for(auto &p:t[v].nxt){
  31.                 char c=p.first; int u=p.second;
  32.                 int j=t[v].link;
  33.                 while(j&&!t[j].nxt.count(c)) j=t[j].link;
  34.                 if(t[j].nxt.count(c)) j=t[j].nxt[c];
  35.                 t[u].link=j;
  36.                 for(int x:t[j].out) t[u].out.push_back(x);
  37.                 q.push(u);
  38.             }
  39.         }
  40.     }
  41.     void search(const string &s,const vector<int> &L,vector<vector<int>> &res){
  42.         int v=0;
  43.         for(int i=0;i<(int)s.size();i++){
  44.             char c=s[i];
  45.             while(v&&!t[v].nxt.count(c)) v=t[v].link;
  46.             if(t[v].nxt.count(c)) v=t[v].nxt[c];
  47.             for(int id:t[v].out)
  48.                 res[id].push_back(i - L[id] + 1);
  49.         }
  50.     }
  51. };
  52. int main(){
  53.     ios::sync_with_stdio(false);
  54.     cin.tie(NULL);
  55.     int n;
  56.     while(cin>>n){
  57.         string tmp;
  58.         getline(cin,tmp);
  59.         vector<string> P(n);
  60.         for(int i=0;i<n;i++) getline(cin,P[i]);
  61.         string T;
  62.         getline(cin,T);
  63.         Aho aho;
  64.         vector<int> L(n);
  65.         for(int i=0;i<n;i++){ L[i]=P[i].size(); aho.add(P[i],i); }
  66.         aho.build();
  67.         vector<vector<int>> occ(n);
  68.         aho.search(T,L,occ);
  69.         for(int i=0;i<n;i++){
  70.             for(int j=0;j<(int)occ[i].size();j++){
  71.                 if(j) cout<<' ';
  72.                 cout<<occ[i][j];
  73.             }
  74.             cout<<'\n';
  75.         }
  76.     }
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0.01s 5328KB
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/yOcesg
language:
C++14 (gcc 8.3)
created:
2 days 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!