请求加强数据

#include<bits/stdc++.h>
using namespace std;

const int N=5e6+10;
int tr[N][30],v[N],fail[N],ts[N],cnt,ti;//ts:时间戳
int val(char c){
	if('a'<=c&&c<='z')return c-'a';
	return 26;
}
void add(string s){
	int tmp=0;
	for(auto ch:s){
		int x=val(ch);
		if(!tr[tmp][x])tr[tmp][x]=++cnt;
		tmp=tr[tmp][x];
	}
	v[tmp]++;
}
void build(){
	queue<int>q;
	while(q.size())q.pop();
	for(int i=0;i<=26;i++){
		if(tr[0][i]){
			fail[tr[0][i]]=0;
			q.push(tr[0][i]);
		}
	}
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=0;i<=26;i++){
			if(tr[u][i]){
				fail[tr[u][i]]=tr[fail[u]][i];
				q.push(tr[u][i]);
			}
			else tr[u][i]=tr[fail[u]][i];
		}
	}
}
int qest(string s){
	ti++;
	int tmp=0,ans=0;
	for(auto ch:s){
		tmp=tr[tmp][val(ch)];
		for(int i=tmp;i&&ts[i]!=ti;i=fail[i]){
			ans+=v[i];
			ts[i]=ti;
		}
	}
	return ans;
}
int n,q;
string s1,s2,t;
string work(string &s1,string &s2){
	t="";
	int l=s1.size(),i,j=l-1;
	for(i=0;i<l;i++){
		if(s1[i]!=s2[i])break;
	}
	if(i==l)return "???";
	for(;j>=0;j--){
		if(s1[j]!=s2[j])break;
	}
	i--;
	j++;
	l=j-i-1;
	t=s1.substr(0,i+1)+"?"+s1.substr(i+1,l)+s2.substr(i+1,l)+"?"+s1.substr(j);
	return t;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>s1>>s2;
		add(work(s1,s2));
	}
	build();
	while(q--){
		cin>>s1>>s2;
		if(s1.size()!=s2.size()){
			cout<<"0\n";
		}
		cout<<qest(work(s1,s2))<<'\n';
	}
    return 0;
}