全 MLE，此题 SAM 有无办法优化空间？

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
int n,lnk[4000005],len[4000005],sz[4000005],lst,top;
map<char,int> nxt[4000005];
vector<int> edge[4000005];
string s,t[200005];
int mkn(){return ++top;}
void ins(char c)
{
	int cur=mkn(),p=lst;len[lst=cur]=len[p]+1;
	while(p>=1&&!nxt[p].count(c)) nxt[p][c]=cur,p=lnk[p];
	if(p<1) return lnk[cur]=1,void();
	int q=nxt[p][c];
	if(len[q]==len[p]+1) return lnk[cur]=q,void();
	int cpy=mkn();nxt[cpy]=nxt[q];
	lnk[cpy]=lnk[q];len[cpy]=len[p]+1;lnk[q]=lnk[cur]=cpy;
	while(p>=1&&nxt[p][c]==q) nxt[p][c]=cpy,p=lnk[p];
}
void dfs(int now)
{
	for(int nxt:edge[now]) dfs(nxt),sz[now]+=sz[nxt];
}
int main()
{
	scanf("%d",&n);lst=mkn();
	for(int i=1;i<=n;i++) cin>>t[i];cin>>s;
	for(int i=0;i<s.length();i++) ins(s[i]);
//	for(int i=0;i<=top;i++)
//		for(char j='a';j<='z';j++)
//			if(nxt[i].count(j)) printf("%d %d %c\n",i,nxt[i][j],j);
	for(int i=1;i<=top;i++) /*cout<<lnk[i]<<' '<<i<<endl,*/edge[lnk[i]].push_back(i);
//	cout<<"cp\n";
	for(int cur=1,i=1;i<=s.length();i++) cur=nxt[cur][s[i-1]],sz[cur]=1/*,cout<<cur<<' ';puts("")*/;
	dfs(1);
	for(int i=1;i<=n;i++)
	{
		int cur=1;
		for(int j=0;j<t[i].length();j++)
		{
			cur=nxt[cur][t[i][j]];
//			printf("%d ",cur);
			if(!cur) break;
		}
		if(cur) printf("%d\n",sz[cur]);
		else printf("0\n");
	}
	return 0;
}