AC自动机50ptsTLE求条

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+7;
int num[N];
struct node{
	int ch[28];
	int end;
	int fail;
}t[N];
int cnt=0,d[N];
int insert(string s){
	int p=0;
	for(int i=0;i<s.size();i++){
		int str=s[i]-'a';
		if(s[i]=='#') str=26;
		if(s[i]=='&') str=27;
		if(!t[p].ch[str])
			t[p].ch[str]=++cnt;
		p=t[p].ch[str];
	}
	return p;
} 
void Fail(){
	queue<int>q;
	for(int i=0;i<=27;i++)
		if(t[0].ch[i]) q.push(t[0].ch[i]);
	while(!q.empty()){
		int p=q.front();
		q.pop();
		for(int i=0;i<=27;i++)
			if(t[p].ch[i]){
				t[t[p].ch[i]].fail=t[t[p].fail].ch[i];
				d[t[t[p].ch[i]].fail]++;
				q.push(t[p].ch[i]); 
			}
			else 
				t[p].ch[i]=t[t[p].fail].ch[i];
	}
}
int n,m;
int sum[N];
int ans=0;
void query(string s){
	int p=0;
	for(char v:s){
		int str=v-'a';
		if(v=='#') str=26;
		if(v=='&') str=27;
		p=t[p].ch[str];
		sum[p]++;
	}
}
int dd[N];
void top(){
	queue <int> q;
	memcpy(dd,d,sizeof(dd));
	for(int i=1;i<=cnt;i++)
		if(!dd[i]) q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		int v=t[u].fail;
		dd[v]--;
		sum[v]+=sum[u];
		if(!dd[v]) q.push(v);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	string s="";
	for(int q=1;q<=n;q++){
		string u,v;
		cin>>u>>v;	
		int i=0,j=u.size()-1;
		string s2="";
		for(;i<u.size();i++){
			if(u[i]!=v[i]) break;
			s2+=u[i];
		}
		for(;j>=0;j--)
			if(u[j]!=v[j]) break;
		s2.append("#");
		for(int k=i;k<=j;k++)
			s2+=u[k];
		for(int k=i;k<=j;k++)
			s2+=v[k];
		s2.append("#");
		j++;
		for(;j<u.size();j++)
			s2+=u[j];
		num[q]=insert(s2);
	}Fail();
	int last=0;
	for(int q=1;q<=m;q++){
		string u,v;
		cin>>u>>v;
		int i=0,j=u.size()-1;
		string s2="";
		for(;i<u.size();i++){
			if(u[i]!=v[i]) break;
			s2+=u[i];
		}
		for(;j>=0;j--)
			if(u[j]!=v[j]) break;
		s2.append("#");
		for(int k=i;k<=j;k++)
			s2+=u[k];
		for(int k=i;k<=j;k++)
			s2+=v[k];
		s2.append("#");
		j++;
		for(;j<u.size();j++)
			s2+=u[j];
		int p=0;
		memset(sum,0,sizeof(sum));
		query(s2);
		top();
		int ans=0;
		for(int i=1;i<=n;i++)
			ans+=sum[num[i]];
		cout<<ans<<"\n";
	}
	return 0;
}