记录编号	609304	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP-S 2025 T3]谐音转换	最终得分	100
用户昵称	梦那边的美好TE	是否通过	通过
代码语言	C++	运行时间	5.063 s
提交时间	2025-11-06 18:53:13	内存使用	107.08 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int tr[N][27],fail[N],sum[N],idx,n,q;
string s,t,p;
queue<int>que;
void insert(string s){
	int p=0,len=s.size();
	for(int i=0,ch;i<len;i++){
		ch=s[i]-'a';
		if(!tr[p][ch])tr[p][ch]=++idx;
		p=tr[p][ch];
	}
	sum[p]++;
	return;
}
void build(){
	for(int i=0;i<=26;i++){
		if(tr[0][i])que.push(tr[0][i]);
	}
	while(que.size()){
		int x=que.front();que.pop();
		for(int i=0;i<=26;i++){
			if(tr[x][i]){
				fail[tr[x][i]]=tr[fail[x]][i];
				que.push(tr[x][i]);
			}
			else tr[x][i]=tr[fail[x]][i];
		}
		sum[x]+=sum[fail[x]];
	}
	return;
}
int ask(string s){
	int p=0,res=0,len=s.size();
	for(int i=0;i<len;i++){
		p=tr[p][s[i]-'a'];
		res+=sum[p];
	}
	return res;
}
int main(){
	freopen("replace.in","r",stdin);
	freopen("replace.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>s>>t;p="";
		if(s==t)continue;
		int l=0,r=s.size()-1;
		while(s[l]==t[l])l++;
		while(s[r]==t[r])r--;
		for(int j=0;j<l;j++)p.push_back(s[j]);
		p.push_back('{');
		for(int j=l;j<=r;j++)p.push_back(s[j]);
		for(int j=l;j<=r;j++)p.push_back(t[j]);
		p.push_back('{');
		for(int j=r+1;j<s.size();j++)p.push_back(t[j]);
		insert(p);
	}
	build();
	for(int i=1;i<=q;i++){
		cin>>s>>t;p="";
		if(s.size()!=t.size())continue;
		int l=0,r=s.size()-1;
		while(s[l]==t[l])l++;
		while(s[r]==t[r])r--;
		for(int j=0;j<l;j++)p.push_back(s[j]);
		p.push_back('{');
		for(int j=l;j<=r;j++)p.push_back(s[j]);
		for(int j=l;j<=r;j++)p.push_back(t[j]);
		p.push_back('{');
		for(int j=r+1;j<s.size();j++)p.push_back(t[j]);
		cout<<ask(p)<<'\n';
	}
	return 0;
}