每次匹配都不停跳fail显然太慢了，于是在每个节点和fail指向的点连一条边，构成一棵树，在这棵树上差分一下就好了。
AC自动机 就这个算法而言其实没用想象中那么难。#include#include #include using namespace std;struct Node{ int fail, next[26], num;}AC[200010];int n, u, cnt;queue q;int p[200010], vis[200010];char a[2000010];int f[200010];struct Edge{ int next, to;}e[200010];int head[200010], num;inline void Add(int from, int to){ e[++num].to = to; e[num].next = head[from]; head[from] = num;}void insert(int x){ int len = strlen(a + 1), w; u = 0; for(int i = 1; i <= len; ++i){ w = a[i] - 'a'; if(!AC[u].next[w]) AC[u].next[w] = ++cnt; u = AC[u].next[w]; } f[x] = u;}void BuildFail(){ u = 0; for(int i = 0; i < 26; ++i) if(AC[u].next[i]) q.push(AC[u].next[i]); while(q.size()){ u = q.front(); q.pop(); for(int i = 0; i < 26; ++i) if(AC[u].next[i]){ q.push(AC[u].next[i]); AC[AC[u].next[i]].fail = AC[AC[u].fail].next[i]; } else AC[u].next[i] = AC[AC[u].fail].next[i]; }}void Match(){ int len = strlen(a + 1); u = 0; for(int i = 1; i <= len; ++i){ u = AC[u].next[a[i] - 'a']; ++vis[u]; }}void dfs(int x){ for(int i = head[x]; i; i = e[i].next){ dfs(e[i].to); vis[x] += vis[e[i].to]; }}int main(){ scanf("%d", &n); for(int i = 1; i <= n; ++i) f[i] = i; for(int i = 1; i <= n; ++i){ scanf("%s", a + 1); insert(i); } scanf("%s", a + 1); BuildFail(); Match(); for(int i = 1; i <= cnt; ++i) Add(AC[i].fail, i); dfs(0); for(int i = 1; i <= n; ++i) printf("%d\n", vis[f[i]]); return 0;}