fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  4. #define pii pair<int,int>
  5. #define pli pair<ll,int>
  6. #define pil pair<int,ll>
  7. #define pll pair<ll,ll>
  8. #define fi first
  9. #define se second
  10. #define MASK(i) (1ll<<i)
  11. #define bit(mask,i) ((mask>>i)&1)
  12. #define el '\n'
  13. #define debug cout << "NOBUG" << endl;
  14. #define pb push_back
  15. #define ALL(vec) vec.begin(),vec.end()
  16. #define File(NAME) freopen(NAME".inp" , "r" , stdin); freopen(NAME".out", "w" , stdout);
  17.  
  18. using namespace std;
  19. const int mod = 1e9+7 , oo = 0x3f3f3f3f;
  20. const ll ooll = 0x3f3f3f3f3f3f3f3f;
  21.  
  22. template <class X , class Y>
  23. bool maximize(X &x , Y y) {
  24.     if(x < y) {
  25.         x = y;
  26.         return true;
  27.     }
  28.     return false;
  29. }
  30. template <class X , class Y>
  31. bool minimize(X &x , Y y) {
  32.     if(x > y) {
  33.         x = y;
  34.         return true;
  35.     }
  36.     return false;
  37. }
  38. template <class X , class Y>
  39. void add_mod(X &x , Y y , int mod) {
  40.     x += y;
  41.     if(x >= mod) x-=mod;
  42.     if(x < 0) x += mod;
  43. }
  44.  
  45. const int NUMBER_OF_NODES = 1e6+5;
  46.  
  47. struct Node {
  48.     int child[26] , next[26];
  49.     int fail;
  50.     vector <int> found;
  51. }node[NUMBER_OF_NODES];
  52.  
  53. struct AC {
  54.     int curCnt = 0;
  55.     inline int newNode() {
  56.         curCnt++;
  57.  
  58.         Node &curNode = node[curCnt];
  59.  
  60.         for(int c = 0 ; c < 26 ; c++) {
  61.             curNode.child[c] = -1;
  62.             curNode.next[c] = -1;
  63.         }
  64.         curNode.fail = -1;
  65.         curNode.found.clear();
  66.  
  67.         return curCnt;
  68.     }
  69.  
  70.     int root = newNode();
  71.  
  72.     void add(string s , int id) {
  73.         int p = root;
  74.         for(char c : s) {
  75.             if(node[p].child[c-'a'] == -1) node[p].child[c-'a'] = newNode();
  76.             p = node[p].child[c-'a'];
  77.         }
  78.         node[p].found.pb(id);
  79.     }
  80.  
  81.     void bfs() {
  82.         node[root].fail = root;
  83.         for(int c = 0 ; c < 26 ; c++) {
  84.             node[root].next[c] = (node[root].child[c] != -1 ? node[root].child[c] : root);
  85.         }
  86.  
  87.         queue <int> q;
  88.         q.push(root);
  89.  
  90.         while(q.size()) {
  91.             int u = q.front();q.pop();
  92.  
  93.             for(int c = 0 ; c < 26 ; c++)if(node[u].child[c] != -1) {
  94.                 int v = node[u].child[c];
  95.  
  96.                 node[v].fail = (u == root ? root : node[node[u].fail].next[c]);
  97.                 for(int c = 0 ; c < 26 ; c++) {
  98.                     node[v].next[c] = (node[v].child[c] != -1 ? node[v].child[c] : node[node[v].fail].next[c]);
  99.                 }
  100.  
  101.                 for(int x : node[node[v].fail].found) {
  102.                     node[v].found.pb(x);
  103.                 }
  104.  
  105.                 q.push(v);
  106.             }
  107.         }
  108.     }
  109. }Aho;
  110.  
  111. // found do not very necessary , if you have to count the number of appearance of Si , just do back dfs like in kmp
  112. // i do not sure about if found can cause mle to my code , so just do not use it
  113. // it is so risky
  114.  
  115. int main() {
  116.     fast
  117.     File("TASK");
  118.     int n; cin >> n;
  119.     for(int i = 1 ; i <= n ; i++) {
  120.         string s; cin >> s;
  121.         Aho.add(s , i);
  122.     }
  123.  
  124.     Aho.bfs();
  125.  
  126.     string t; cin >> t;
  127.     int p = Aho.root;
  128.     for(int i = 0 ; i < t.size(); i++) {
  129.         int c = t[i]-'a';
  130.         p = node[p].next[c];
  131.         cout << p << ':';
  132.         for(int x : node[p].found) cout << x << ' ';
  133.         cout << el;
  134.     }
  135.     return 0;
  136. }
  137. /*
  138. input:
  139. 6
  140. di
  141. du
  142. didu
  143. dudua
  144. duadi
  145. didi
  146. diduduadi
  147. output:
  148. 2|
  149. 3|1
  150. 5|
  151. 6|3 2
  152. 7|
  153. 8|2
  154. 9|4
  155. 11|
  156. 12|5 1
  157. */
  158.  
Success #stdin #stdout 0.08s 238228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4Wx9zM
language:
C++ (gcc 8.3)
created:
9 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!