先贴我队友的AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=200006,M=2000006;
int n,trie[M][26],f[M],last[M],ans[M],to[N],sta[N],top,cnt;
bool ed[M];
queue <int> que;
char s[N],t[M];
int main(){
	freopen("hack.in","r",stdin);
	freopen("ans.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>s;
		int len=strlen(s),p=0;
		for (int j=0;j<len;j++){
			if (!trie[p][s[j]-'a']) trie[p][s[j]-'a']=++cnt;
			p=trie[p][s[j]-'a'];
		}
		ed[p]=1;
		to[i]=p;
	}
	cin>>t;
	for (int i=0;i<26;i++){
		int u=trie[0][i];
		if (u){	que.push(u);f[u]=0,last[u]=0;} 
	}
	while (!que.empty()){
		int h=que.front();
		for (int i=0;i<26;i++){
			int u=trie[h][i];
			if (!u){trie[h][i]=trie[f[h]][i];continue;} 
			que.push(u);
			f[u]=trie[f[h]][i];
			last[u]=ed[f[u]]>0?f[u]:last[f[u]];
		}
		que.pop();
	}
	int len=strlen(t),j=0;
	for (int i=0;i<len;i++){
		j=trie[j][t[i]-'a'];
		for (int e=j;e>0;e=last[e]) ans[e]++;
	}
	for (int i=1;i<=n;i++) cout<<ans[to[i]]<<endl;
	
	return 0;
}

其实是在暴力跳时只跳表示整个模式串的状态：

last[u]=ed[f[u]]>0?f[u]:last[f[u]];

但是在大量模式串是其中一个的后缀时，就会退化为暴力跳。

hack数据程序：

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("hack.in","w",stdout);
	cout<<631<<endl;
	for(int i=1;i<=631;i++){
		for(int j=1;j<=i;j++) cout<<'a';
		cout<<endl;
	}
	for(int i=1;i<=2000000;i++){
		cout<<'a';
	}
	cout<<endl;
	return 0;
}