建议加强数据

#include<bits/stdc++.h>
using namespace std;
string x2[200000],y2[200000],x,y;long long tp[10000],po,si[200000],bsi[200000],ht1[200000],ht2[200000],ha3[5000000],ha4[5000000],ba[6000000],yu[5000000];
unordered_map<long long,long long> sp;unordered_map<long long,long long> sq;
long long geha(long long l,long long r,long long m,long long v){
	long long ftl,ftr;
    if(m==2){
		ftl=ha3[r];ftr=(l==0?0:ha3[l-1]);
	}else{
		ftl=ha4[r];ftr=(l==0?0:ha4[l-1]);
	}
	return ((ftl-ftr*ba[r-l+1]&((1<<30)-1))&((1<<30)-1)+(1<<30))&((1<<30)-1);
}
bool sort2(string a,string b){
	return a.size()<b.size();
}
string read(){
	char c=getchar();string s;
	while(c<'a' || c>'z'){
		c=getchar();
	}
	while(c>='a' && c<='z'){
		s+=c;
		c=getchar();
	}
	return s;
}
int main(){
	long long va=1,ans=0;
	for(long long j=0;j<6000000;j++){
		ba[j]=va;va=va*31&((1<<30)-1);
	}
	long long n,q;cin>>n>>q;
	for(long long j=0;j<n;j++){
		x2[j]=read();y2[j]=read();
	}
	stable_sort(x2,x2+n,sort2);
	stable_sort(y2,y2+n,sort2);
	for(long long j=0;j<n;j++){
		si[j]=x2[j].size();
		long long z=0,z2=0;
		for(long long t=0;t<x2[j].size();t++){
			z=z*31+x2[j][t]-96;
			z&=((1<<30)-1);
			z2=z2*31+y2[j][t]-96;
			z2&=((1<<30)-1);
			long long man;
			man=(z<<30)+z2;
			pair<long long,long long> ma2;
			ma2.first=man;ma2.second=1;
			sq.insert(ma2);
		}
		long long man;
		man=(z<<30)+z2;
		pair<long long,long long> ma2;
		ma2.first=man;ma2.second=1;
		if(sp.find(man)!=sp.end()){
			sp.find(man)->second++;
		}else{
			sp.insert(ma2);
		}
    ht1[j]=z;ht2[j]=z2;
    if(j==0 || si[j]!=si[j-1]){
      tp[po]=si[j];po++;
		}
	}
	for(long long j=0;j<q;j++){
		x=read();y=read();ans=0;
		x=char(123)+x+char(123);y=char(123)+y+char(123);
		if(x.size()!=y.size()){
			cout<<0<<endl;
		}else{
		long long z=0,z2=0;
		for(long long t=0;t<x.size();t++){
			z=z*31+x[t]-96;
			z&=((1<<30)-1);
			z2=z2*31+y[t]-96;
			z2&=((1<<30)-1);
			ha3[t]=z;ha4[t]=z2;
		}
		long long tl=-1,tr=-1;
		for(long long t=0;t<x.size();t++){
			if(x[t]!=y[t]){
				tr=t;
				if(tl==-1){
					tl=t;
				}
			}
		}
		long long man,ts,tn;
		for(long long t=0;t<=tl;t++){
			ts=lower_bound(tp,tp+po,tr-t+1,less<long long>())-tp,tn=upper_bound(tp,tp+po,x.size()-t+1,less<long long>())-tp-1;
			for(long long u=ts;u<=tn;u++){
				man=(geha(t,t+tp[u]-1,2,0)<<30)+geha(t,t+tp[u]-1,3,0);
				if(sq.find(man)==sq.end()){
					break;
				}
				if(sp.find(man)!=sp.end()){
					ans+=sp.find(man)->second;
				}
			}
		}
		cout<<ans<<'\n';
		}
	}
}