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.     int n;
  66.     while(cin>>n){
  67.         vector<int> s_size(n);
  68.         aho_corasick ac;
  69.         for(int a=0;a<n;a++){
  70.             string s;
  71.             getline(cin,s);
  72.             ac.add_string(s,a);
  73.             s_size[a]=s.size();
  74.         }
  75.         ac.build_automaton();
  76.         vector<int> ans[n];
  77.         string t;
  78.         getline(cin,t);
  79.         int p=0;
  80.         for(int i=0;i<t.size();i++){
  81.             p=ac.g[p].nxt[t[i]];
  82.             for(int j:ac.get_sidx(p)){
  83.                 ans[j].push_back(i-s_size[j]+1);
  84.             }
  85.         }
  86.         for(vector<int> v:ans){
  87.             if(!v.size()) cout<<"\n";
  88.             else{
  89.                 for(int i:v){
  90.                     cout<<i<<" ";
  91.                 }
  92.                 cout<<"\n";
  93.             }
  94.         }
  95.     }
  96. }*/
  97. signed main(){
  98.     cin.tie(0)->sync_with_stdio(0);
  99.     string n_line;
  100.     while (getline(cin, n_line)){
  101.         int n = stoi(n_line);
  102.  
  103.         vector<int> s_size(n);
  104.         aho_corasick ac;
  105.         for (int i=0; i<n; i++){
  106.             string s; getline(cin, s);
  107.             ac.add_string(s, i);
  108.             s_size[i] = s.size();
  109.         }
  110.         ac.build_automaton();
  111.  
  112.         vector<vector<int>> result(n);
  113.         string t; getline(cin, t);
  114.         for (int i=0, p=0; i<t.size(); i++){
  115.             p = ac.g[p].nxt[t[i]];
  116.             for (int j: ac.get_sidx(p))
  117.                 result[j].push_back(i - s_size[j] + 1);
  118.         }
  119.  
  120.         for (const vector<int> &v: result){
  121.             if (v.size() == 0) cout << "\n";
  122.             else for (int i=0; i<v.size(); i++)
  123.                 cout << v[i] << " \n"[i == v.size()-1];
  124.         }
  125.     }
  126. }
  127.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
2
p
pup
Popup
stdout
copy 
2 4
2
https://ideone.com/aUCFWR
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!