AC自动机TLE70分求助 悬2关

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e6+10;
struct tree{
	int vis[28];
	int fail,used,end;
}AC[N];
int n,q,tot;
string s1[N],s2[N];
void build(){
	for(int i=1;i<=n;i++){
		if(s1[i]==s2[i]) continue;
		int now=0;
		for(int j=0;j<s1[i].size();j++){
			if(!AC[now].vis[s1[i][j]-'a']) AC[now].vis[s1[i][j]-'a']=++tot;
			now=AC[now].vis[s1[i][j]-'a'];
	//		cout<<now<<" "<<tot<<" "<<s1[i][j]<<endl;
		}
		AC[now].end++;
	}
}
void make(){
	queue<int> q;
	for(int i=0;i<=27;i++) if(AC[0].vis[i]) q.push(AC[0].vis[i]);
	while(!q.empty()){
		int u=q.front();
	//	cout<<u<<endl;
		q.pop();
		for(int i=0;i<=27;i++){
			if(AC[u].vis[i]){
	//			cout<<u<<" "<<i<<" "<<AC[u].vis[i]<<endl;
				q.push(AC[u].vis[i]);
				AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
			}
			else AC[u].vis[i]=AC[AC[u].fail].vis[i];
		}
	}
}
inline int query(string t){
	vector<int> add;
	int cnt=0,now=0;
	for(int i=0;i<t.size();i++){
		now=AC[now].vis[t[i]-'a'];
		for(int j=now;j&&AC[j].used==0;j=AC[j].fail){
			cnt+=AC[j].end;
			add.push_back(j);
			AC[j].used=1;
		}
	}
	for(auto i:add) AC[i].used=0;
	return cnt;
}
inline string turn(string n1,string n2){
	string s="";
	int fr=0,en=0;
	for(int i=0;i<n1.size();i++) if(n1[i]!=n2[i]) {
		fr=i;
		break;
	} 
	for(int i=n1.size()-1;i>=0;i--) if(n1[i]!=n2[i]){
		en=i;
		break;
	}
	for(int i=0;i<fr;i++) s+=n1[i];
	s+='{';
	for(int i=fr;i<=en;i++) s+=n1[i];
	for(int i=fr;i<=en;i++) s+=n2[i];
	s+='{';
	for(int i=en+1;i<n1.size();i++) s+=n1[i];
	return s;
}
signed main(){
//	freopen("replace3.in","r",stdin);
//	freopen("replace.out","w",stdout);
	//cout<<(char)('a'+26)<<endl;
//	cout<<turn("aaababa","aaabcbc")<<endl;
//	return 0;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>s1[i]>>s2[i];
		s1[i]=turn(s1[i],s2[i]);
	//	cout<<i<<" "<<s1[i]<<endl;
	}
	build();
	make();
//	cout<<"FXXkCCF"<<endl;
	while(q--){
		string t1,t2;
		cin>>t1>>t2;
//		if(t1==t2) cout<<"SSS"<<endl;
//		cout<<turn(t1,t2)<<endl;
		if(t1.size()!=t2.size()) cout<<0<<'\n';
		else cout<<query(turn(t1,t2))<<'\n';
	}
	return 0;
}