求复杂度

#include<bits/stdc++.h>
using namespace std;
const int NR=5e6+5;
int n,q;
int ch[NR][27],sz;
int fail[NR];
int cnt[NR],vis[NR];
string LCZ(const string& s1,const string& s2){
	int n=s1.size();
	int l=0,r=n;
	while(l<n&&s1[l]==s2[l]) l++;
	while(r>=0&&s1[r]==s2[r]) r--;
	string ret="";
	ret+=s1.substr(0,l);
	ret+='{';
	if(r>=l){
		ret+=s1.substr(l,r-l+1);
		ret+=s2.substr(l,r-l+1);
	}
	ret+='{';
	if(r<n) ret+=s1.substr(r+1,n-r);
	return ret;
}
void insert(const string& s){
	int cur=0;
	for(int i=0;i<s.size();i++){
		if(!ch[cur][s[i]-'a']) ch[cur][s[i]-'a']=++sz;
		cur=ch[cur][s[i]-'a'];
	}
	cnt[cur]++;
}
void build(){
	queue<int> q;
	for(int i=0;i<27;i++){
		if(ch[0][i]) q.push(ch[0][i]);
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<27;i++){
			int y=ch[x][i];
			if(y){
				fail[y]=ch[fail[x]][i];
				q.push(y);
			}
			else ch[x][i]=ch[fail[x]][i];
		}
	}
}
int query(const string& s,int col){
	int cur=0,ret=0;
	for(int i=0;i<s.size();i++){
		cur=ch[cur][s[i]-'a'];
		for(int j=cur;j&&vis[j]!=col;j=fail[j]){
			ret+=cnt[j];
			vis[j]=col;
		}
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		string s1,s2;
		cin>>s1>>s2;
		insert(LCZ(s1,s2));
	}	
	build();
	for(int i=1;i<=q;i++){
		string t1,t2;
		cin>>t1>>t2;
		cout<<query(LCZ(t1,t2),i)<<"\n";
	}
	return 0;
}