将一个变换 $S_1 \rightarrow S_2$ 表示为 $ABC \rightarrow ADC$，其中 $A,C$ 是最长公共前后缀，那么将其转换为 $S=A?BD?C$，其中 $?$ 为特殊字符。$T_1 \rightarrow T_2$ 同理。那么 $S$ 合法当且仅当其作为 $T$ 的子串出现，直接跑多模匹配即可。用 AC 自动机解决，时间复杂度线性乘字符集大小。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=2e5+10,mxl=6e6+10; 
int n,q;
int ch[mxl][30],ed[mxl],fail[mxl],id;
void ins(string s){
	int p=0;
	for(int i=0;i<s.size();i++){
		int j=(s[i]>='a'&&s[i]<='z')?s[i]-'a':26;
		if(!ch[p][j])ch[p][j]=++id;
		p=ch[p][j];
	}
	ed[p]++;
}
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();
		ed[x]+=ed[fail[x]];
		for(int i=0;i<27;i++){
			int &y=ch[x][i];
			if(!y)y=ch[fail[x]][i];
			else fail[y]=ch[fail[x]][i],q.push(y);
		}
	}
}
int find(string s){
	int ans=0,p=0;
	for(int i=0;i<s.size();i++){
		int j=(s[i]>='a'&&s[i]<='z')?s[i]-'a':26;
		p=ch[p][j];
		ans+=ed[p];
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		string s1,s2;
		cin>>s1>>s2;
		int len=s1.size();
		int l=0,r=len-1;
		while(l<=r&&s1[l]==s2[l])l++;
		while(l<=r&&s1[r]==s2[r])r--;
		if(l>r)continue;
		string s=s1.substr(0,l)+"#"+s1.substr(l,r-l+1)+s2.substr(l,r-l+1)+"#"+s1.substr(r+1);
		ins(s);
	}
	build();
	for(int i=1;i<=q;i++){
		string s1,s2;
		cin>>s1>>s2;
		int len=s1.size();
		int l=0,r=len-1;
		while(l<=r&&s1[l]==s2[l])l++;
		while(l<=r&&s1[r]==s2[r])r--;
		if(l>r)continue;
		string s=s1.substr(0,l)+"#"+s1.substr(l,r-l+1)+s2.substr(l,r-l+1)+"#"+s1.substr(r+1);
		cout<<find(s)<<'\n';
	}
	return 0;
}

string 从 1 开始遍历没绷住。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e6+10;
int ch[N][27],pre[N],len,ed[N];
void ins(string s,int x)
{
	int n=s.size(),p=0;
	for(int i=0;i<n;i++)
	{
		int j=s[i]-'a';
		if(!ch[p][j])ch[p][j]=++len;
		p=ch[p][j];
	}
	ed[p]++;
}
void build()
{
	deque<int>q;
	for(int i=0;i<27;i++)if(ch[0][i])q.push_back(ch[0][i]);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();ed[x]+=ed[pre[x]];
		for(int j=0;j<27;j++)
		{
			int y=ch[x][j];
			if(!y)ch[x][j]=ch[pre[x]][j];
			else pre[y]=ch[pre[x]][j],q.push_back(y);
		}
	}
}
string init(string s1,string s2)
{
	int pos1=-1,pos2=s2.size();
	while(s1[pos1+1]==s2[pos1+1])pos1++;
	while(s1[pos2-1]==s2[pos2-1])pos2--;
	int pos=0;string st="";
	for(int i=0;i<=pos1;i++)st+=s1[i];
	st+='{';
	for(int i=pos1+1;i<pos2;i++)st+=s1[i];
	for(int i=pos1+1;i<pos2;i++)st+=s2[i];
	st+='{';
	for(int i=pos2;i<s2.size();i++)st+=s1[i];
	return st;
}
signed main()
{
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		string s1,s2;cin>>s1>>s2;
		string ss=init(s1,s2);
		ins(ss,i);
	}
	build();
	while(q--)
	{
		string s1,s2;cin>>s1>>s2;
		string ss=init(s1,s2);int len=ss.size();
		int p=0,ans=0;
		for(int i=0;i<len;i++)
		{
			p=ch[p][ss[i]-'a'];
			ans+=ed[p];
		}
		cout<<ans<<'\n';
	}
	return 0;
}