fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define FOR(i,j,k) for(int i=j;i<=k;i++)
  6. #define PB push_back
  7. #define MAX 100010
  8.  
  9. struct node
  10. {
  11.     char ch;
  12.  
  13.     node *next[26], *fail, *pa;
  14.     vector<int> output;
  15.  
  16.     node()
  17.     {
  18.         pa = fail = NULL;
  19.         FOR(i,0,25) next[i] = NULL;
  20.     }
  21. };
  22.  
  23. node *Root;
  24.  
  25. int ID(char ch)
  26. {
  27.     int ret = 0;
  28.  
  29.     if(ch < 'a') ret = ch - 'A';
  30.     else ret = ch - 'a';
  31.  
  32.     return ret;
  33. }
  34.  
  35. void in(string str,int p)
  36. {
  37.     node *s = Root;
  38.     int n = str.size();
  39.  
  40.     FOR(i,0,n-1)
  41.     {
  42.         int x = ID( str[i] );
  43.  
  44.         if(s->next[x] == NULL)
  45.         {
  46.             s->next[x] = new node();
  47.             s->next[x]->ch = str[i];
  48.             s->next[x]->pa = s;
  49.         }
  50.         s = s->next[x];
  51.     }
  52.  
  53.     if(!s->output.size())
  54.     {
  55.         s->output.PB( p );
  56.     }
  57.     return;
  58. }
  59.  
  60. queue<node*> que;
  61.  
  62. void outputLink(node *go,node *p)
  63. {
  64.     for(auto oto : go->output) p->output.PB( oto );
  65. }
  66.  
  67. void bfs(node *p)
  68. {
  69.     que.push( p );
  70.  
  71.     while(!que.empty())
  72.     {
  73.         p = que.front(); que.pop();
  74.         int C = ID( p->ch );
  75.         //cout << p->ch << endl;
  76.  
  77.         if(p->pa == Root)
  78.         {
  79.             p->fail = Root;
  80.         }
  81.         else
  82.         {
  83.             node *s = p->pa->fail;
  84.  
  85.             while(true)
  86.             {
  87.                 ///cout << s->lev << ' ' << s->ch << endl;
  88.                 if(s->next[C] != NULL)
  89.                 {
  90.                     p->fail = s->next[C];
  91.                     outputLink(s->next[C], p);
  92.                     break;
  93.                 }
  94.                 else if(Root == s)
  95.                 {
  96.                     p->fail = Root;
  97.                     break;
  98.                 }
  99.  
  100.                 s = s->fail;
  101.             }
  102.         }
  103.  
  104.         FOR(i,0,25)
  105.         {
  106.             if(p->next[i] != NULL)
  107.             {
  108.                 que.push( p->next[i] );
  109.             }
  110.         }
  111.     }
  112.  
  113. }
  114.  
  115.  
  116. string pattern[MAX], text;
  117. vector<int> ocr[MAX];
  118.  
  119. void readText()
  120. {
  121.     int p = 0, n = text.size(), x;
  122.     node *s = Root;
  123.  
  124.     while(p < n)
  125.     {
  126.         int x = ID( text[p] );
  127.         if(s->next[x] != NULL)
  128.         {
  129.             s = s->next[x];
  130.             for(auto go : s->output)
  131.             {
  132.                 ocr[p].PB( go );
  133.             }
  134.             p++;
  135.         }
  136.         else if(s == Root) p++;
  137.         else s  = s->fail;
  138.     }
  139. }
  140.  
  141. int main()
  142. {
  143.     ios::sync_with_stdio(false);
  144.     ///freopen("in.txt", "r", stdin);
  145.    // freopen("out.txt", "w", stdout);
  146.  
  147.     Root = new node();
  148.     Root->fail = Root;
  149.     Root->pa = Root;
  150.  
  151.     int n, q;
  152.  
  153.     cin >> n;
  154.     cin >> text;
  155.  
  156.     cin >> q;
  157.     FOR(i,0,q-1)
  158.     {
  159.         cin >> pattern[i];
  160.         in(pattern[i], i);
  161.     }
  162.  
  163.     bfs( Root );
  164.     readText();
  165.  
  166.     return 0;
  167. }
  168.  
Success #stdin #stdout 0s 8492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sPGOwN
language:
C++ (gcc 8.3)
created:
5 years 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!