题目大意

给定$n$个形如$s\space t$的变换规则，再询问$q$次，每次询问给出两个字符串$s$和$t$，计算有多少种单次替换能将$s$变为$t$。

---

题目分析

要从$s$中找替换规则中的子串，显然是一个多模式匹配问题，可以使用AC自动机解决。
接下来就该思考如何将两个字符串转换为一个字符串，因为AC自动机适用于单个串匹配，如果不进行转换，每次都要以$O(|t|)$的时间复杂度比较。以下思路参考了洛谷用户@Register_int：
把变换$s\rightarrow t$记为$A?CD?B$，其中$A,B,C,D$都为字符串，$A$和$B$分别表示$s$和$t$的最长公共前缀和后缀，$C$和$D$分别表示$s$和$t$其它的部分，对询问也进行同样的变换。
正确性说明：若变换$s\rightarrow t$是一个合法的变换，设它表示为$E?GH?F$，$E$实际上不会影响开头和结尾未触及的部分，即未被修改的部分必然完全相同，且这部分就位于字符串的两端。而中间需要进行变换的部分，$G$一定对应$C$，$H$一定对应$D$，即改变了需要改变的位置。这样不需要改变的部分没有改变，需要改变的部分改变了，即这个变换可行。
变换中的$?$可以变为'{'，因为它位于$'z'$之后。

变换代码如下：

inline string sub(string s,int l,int r) {return s.substr(l,r-l+1);} //求子串
inline string f(string s,string t)
{
	int i=0,j=0,len=min(s.size(),t.size());
	while (i<len && s[i]==t[i]) i++; //找最长公共前缀
	while (j<len && s[s.size()-j-1]==t[t.size()-j-1]) j++; //找最长公共后缀
	return sub(s,0,i-1)+"{"+sub(s,i,s.size()-j-1)+sub(t,i,t.size()-j-1)+"{"+sub(s,s.size()-j,s.size()-1);
}

求$fail$指针和AC自动机操作代码如下：

inline void getfail()
{
	queue<int> q;
	for (int i=0;i<27;i++) //注意是27，辅助字符占用一个
	{
		if (t[0].son[i])
			q.push(t[0].son[i]);
	}
	while (!q.empty())
	{
		int now=q.front();
		q.pop();
		for (int i=0;i<27;i++)
		{
			if (t[now].son[i])
			{
				t[t[now].son[i]].fail=t[t[now].fail].son[i]; //子节点的fail指针=父节点的fail指针的对应子节点
			}
			else
				t[now].son[i]=t[t[now].fail].son[i]; //若不存在，不能不管，否则会忽略特殊情况
		}
	}
}
inline int query(string s)
{
	int now=0,ans=0;
	for (auto c:s)
	{
		c-='a';
		now=t[now].son[c];
		int i=now;
        //last是上一次操作的编号，tot是当前操作编号
        //若last=tot，说明当前操作已经进行，不用再进行
        //这样的好处是不用每次都重置标记，如果只使用bool vis，每次询问后都要清空vis
		while (i && t[i].last!=tot)
			ans+=t[i].end,t[i].last=tot,i=t[i].fail; //不清楚是否有重复变换，因此是+=end，记得更新last
	}
	return ans;
}

这样做时间复杂度最坏情况下能达到$O((\sum_{i=1}^{n} s_{i,1}+s_{i,2})^2)$量级，能得到$90$分。

---

优化

接下来考虑优化。

AC自动机常用的优化方法是拓扑排序优化，但拓扑排序优化需要遍历整个字典树，甚至可能提高时间复杂度，因此拓扑排序优化不可行。

我们注意到，在查询过程中，实际上访问了大量重复字符，一些$end$标记为$0$的节点也被访问了。为了避免这种情况，可以使用后缀链跳跃的方法，为每个节点定义$next$为当前后缀链上下一个有$end$标记的节点，这样操作时每个模式串只访问一次，与$t$的长度无关。

如何求得$next$？分两种情况，若$fail$指针指向的节点带有$end$标记，直接指向它，否则继承它的$next$，代码如下：

if (t[t[t[now].fail].son[i]].end)
    t[t[now].son[i]].nxt=t[t[now].fail].son[i];
else
    t[t[now].son[i]].nxt=t[t[t[now].fail].son[i]].nxt;

这时候$query$函数的$i=t[i].fail$就可以改为$i=t[i].nxt$

---

完整代码

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

int n,cnt=0,tot;
//cnt：字典树大小，tot：当前测试编号
struct node
{
	int son[27],fail,end,last,nxt;
    //end：以当前节点为结尾的字符串数，last：上一次操作时的测试编号，nxt：后缀链上下一个带有标记的节点
} t[5000005];
inline void build(string s) //构建节点
{
	int now=0;
	for (auto c:s)
	{
		c-='a';
		if (!t[now].son[c]) t[now].son[c]=++cnt;
		now=t[now].son[c];
	}
	t[now].end++; //不清楚是否有重复节点，++
}
inline void getfail() //求fail指针
{
	queue<int> q;
	for (int i=0;i<27;i++)
	{
		if (t[0].son[i])
			q.push(t[0].son[i]);
	}
	while (!q.empty())
	{
		int now=q.front();
		q.pop();
		for (int i=0;i<27;i++)
		{
			if (t[now].son[i])
			{
				t[t[now].son[i]].fail=t[t[now].fail].son[i]; //求fail指针
				if (t[t[t[now].fail].son[i]].end) t[t[now].son[i]].nxt=t[t[now].fail].son[i];  //求nxt指针
				else t[t[now].son[i]].nxt=t[t[t[now].fail].son[i]].nxt;
				q.push(t[now].son[i]);
			}
			else
				t[now].son[i]=t[t[now].fail].son[i];
		}
	}
}
inline int query(string s) //查询
{
	int now=0,ans=0;
	for (auto c:s)
	{
		c-='a';
		now=t[now].son[c];
		int i=now;
		while (i && t[i].last!=tot)
			ans+=t[i].end,t[i].last=tot,i=t[i].nxt; //i=t[i].fail升级版
	}
	return ans;
}
inline string sub(string s,int l,int r) {return s.substr(l,r-l+1);} //子串函数，获取[l,r]的子串
inline string f(string s,string t) //变换
{
	int i=0,j=0,len=min(s.size(),t.size());
	while (i<len && s[i]==t[i]) i++;
	while (j<len && s[s.size()-j-1]==t[t.size()-j-1]) j++;
	return sub(s,0,i-1)+"{"+sub(s,i,s.size()-j-1)+sub(t,i,t.size()-j-1)+"{"+sub(s,s.size()-j,s.size()-1);
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	string s,t;
	int q;
	cin >> n >> q;
	for (int i=1;i<=n;i++)
	{
		cin >> s >> t;
		build(f(s,t));
	}
	getfail();
	for (int i=1;i<=q;i++)
	{
		tot=i;
		cin >> s >> t;
		cout << query(f(s,t)) << '\n';
	}
	return 0;
}

---

复杂度分析

空间复杂度显然为$O(L_1)$。
对每个函数分析时间复杂度：

$build$函数：共要插入$L_1$个字符，因此时间复杂度为$O(L_1)$；

$getfail$函数：需要遍历每个节点及其子节点，因此时间复杂度为$O(26L_1)=O(L_1)$；

$query$函数：首先遍历每个询问字符，时间复杂度为$O(L_2)$。每次询问，由于路径压缩优化，每个变换规则至多遍历一次，最坏情况下遍历$n$次。共有$q$次询问，因此时间复杂度$<O(nq+L_2)$；

$f$函数：显然为$O(L_1)$。

因此总时间复杂度上限为$O(nq+L_2)$，测试数据没有那么毒瘤，足以通过测试。