[HDU3065]病毒持续侵袭中（AC自动机）

传送门

AC自动机的又一模板，统计每个字符串在文本中的次数。

所以就不需要vis数组了。

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 5 using namespace std; 6 7 int n, sz; 8 int ch[50001][130], val[50001], fail[50001], ans[50001]; 9 char s[2000001], a[1001][50]; 10 11 inline void insert(int k) 12 20 val[now] = k; 21 } 22 23 inline void make_fail() 24 40 fail[ch[now][i]] = ch[fail[now]][i]; 41 q.push(ch[now][i]); 42 } 43 } 44 } 45 46 inline void ac() 47 58 now = ch[now][x]; 59 } 60 } 61 62 int main() 77 make_fail(); 78 scanf("%s", s); 79 ac(); 80 for(i = 1; i <= n; i++) 81 if(ans[i]) 82 printf("%s: %d\n", a[i], ans[i]); 83 } 84 return 0; 85 }
View Code

上一篇：Monkey King（左偏树）

下一篇：【模板】划分树

---

AC自动机