fork(1) download
  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
stdin
Standard input is empty
stdout
Standard output is empty