给定若干模式串组成的文本串，求每个模式串出现的次数。
由于模式串可能重复，所以直接按照AC自动机的模板会出错，所以我们定义一个same数组，end数组只记录最早的编号，每次如果要覆盖，便把令该节点的same值为这个位置上的end的值，查询一遍，输出答案就输出ans[same[i]]。
我们再定义两个数组vis和sum表示当前节点有没有被扫过，当前节点被覆盖的次数。那么在统计答案的时候，如果当前节点是某个模式串的结尾并且没有扫过，那么说明这个模式串有贡献，就将答案+sum[now],之后将vis赋值为1，这样跑一边AC自动机就可以了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n, tot, same[100010], ans[100010], ch[500010][26], end[500010], vis[500010], sum[500010]; 4 int f[500010]; 5 char c[210][100010]; 6 inline int read() { 7 int ret = 0, op = 1; 8 char c = getchar(); 9 while (!isdigit(c)) { 10 if (c == ‘-‘) op = -1; 11 c = getchar(); 12 } 13 while (isdigit(c)) { 14 ret = ret * 10 + c - ‘0‘; 15 c = getchar(); 16 } 17 return ret * op; 18 } 19 inline void write(int x) { 20 if (x < 0) putchar(‘-‘), x = -x; 21 if (x >= 10) write(x / 10); 22 putchar(x % 10 + ‘0‘); 23 } 24 void insert(char *a, int id) { 25 int now = 0, l = strlen(a); 26 for (int i = 0; i < l; ++i) { 27 if (!ch[now][a[i] - ‘a‘]) ch[now][a[i] - ‘a‘] = ++tot; 28 now = ch[now][a[i] - ‘a‘]; 29 sum[now]++; 30 } 31 if (!end[now]) end[now] = id; 32 else same[id] = end[now]; 33 } 34 queue <int> q; 35 void bfs() { 36 for (register int i = 0; i < 26; ++i) 37 if (ch[0][i]) { 38 f[ch[0][i]] = 0; 39 q.push(ch[0][i]); 40 } 41 while (!q.empty()) { 42 int now = q.front(); 43 q.pop(); 44 for (register int i = 0; i < 26; ++i) { 45 if (ch[now][i]) f[ch[now][i]] = ch[f[now]][i], q.push(ch[now][i]); 46 else ch[now][i] = ch[f[now]][i]; 47 } 48 } 49 } 50 void query(char *a) { 51 int now = 0; 52 int l = strlen(a); 53 for (int i = 0; i < l; ++i) { 54 now = ch[now][a[i] - ‘a‘]; 55 for (register int j = now; j; j = f[j]) 56 if (end[j] && !vis[now]) ans[end[j]] += sum[now]; 57 vis[now] = 1; 58 } 59 } 60 int main() { 61 n = read(); 62 for (register int i = 1; i <= n; ++i) { 63 scanf("%s", c[i]); 64 insert(c[i], i); 65 } 66 bfs(); 67 for (register int i = 1; i <= n; ++i) 68 if (!same[i]) query(c[i]); 69 for (register int i = 1; i <= n; ++i) { 70 if (!same[i]) write(ans[i]); 71 else write(ans[same[i]]); 72 puts(""); 73 } 74 return 0; 75 }
原文：https://www.cnblogs.com/shl-blog/p/11262780.html
