好像是 COGS 首 A，写篇题解。

其实这道题的思维难度不是特别大，只需要一些技巧和比较高级的算法即可解决。

思路分析

注意到对于一对用来替换的字符串二元组 $(s,t)$，若 $s=t$，则这对字符串一定没用，题目已经限制。

对于这对 $s,t$，可以分别将其表示成 $s=s_A+s_C+s_B,t=t_A+t_D+t_B$，其中 $s_A,t_A$ 是 $s,t$ 的最长公共前缀，$s_B,t_B$ 是 $s,t$ 的最长公共后缀，每次替换操作，实际上是将一个字符串中的 $s_C$ 替换成了 $t_D$。

对于一对询问的字符串 $(S,T)$，若长度不相等，则一定没有合法的变化，题目已经限制。

依然求出两个 $S,T$ 的子串 $s_{A,C,B},t_{A,D,B}$（意义同上），若 $(S,T)$ 可以用过 $(s,t)$ 替换得来，当且仅当 $S_C=s_C,T_D=t_D$。

这样的话，我们就可以得到一个 $O(nq)$ 的算法，对于每个变化的字符串二元组和询问，处理出变化的部分，若 $(s,t),(S,T)$ 变化的部分一样，且 $s$ 再 $S$ 中出现，$t$ 在 $T$ 中出现，因为变化的部分要匹配上，所以匹配的起始位置是确定的，可以用字符串 Hash 来完成 $O(1)$ 的判断。

cin>>S>>T;int ans=0;
if(S.size()!=T.size()){
    printf("0\n");
    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<S.size();j++){
    if(j){
        hs[j]=hs[j-1]*P+S[j];
        ht[j]=ht[j-1]*P+T[j];
    }else{
        hs[j]=S[j];
        ht[j]=T[j];
    }
}
for(int j=1;j<=n;j++){
    bool flag=0;
    if(l[j]==-1)continue;
    if(R-L+1!=r[j]-l[j]+1)continue;
    int ll=L-l[j],rr=ll+len[j]-1;
    if(ll<0||rr>=S.size())continue;
    if(askS(ll,rr)!=a[j])continue;
    if(askT(ll,rr)!=b[j])continue;
    ans++;
}
printf("%d\n",ans);

考虑优化这个过程，离线，还是利用字符串 Hash，把变化部分相同的变化字符串和询问字符串放在一起处理。

此时变化部分的匹配一定满足，只需要保证 $s_A$ 是 $S_A$ 的后缀，$t_B$ 是 $T_B$ 的前缀。将所有 $s_A,S_A$ 放在一起建一个字典树，$t_B,T_B$ 放在一起建一个字典树，则前后缀关系可以转化成字典树上的祖先子孙关系，两个字典树就有两维的限制，直接做离散化加二维数点即可，复杂度为 $O(L+(n+q)\log(n+q))$。

这个做法所使用的算法均在提高级的考纲之内，应该是钦定的正解。

其实有一种更加优秀的做法，可以转化为经典的多模式串匹配的算法，但需要 AC 自动机。

考虑将每个字符串对 $(s,t)$ 拼成一个大串 $P=s_A+?+s_C+t_D+?+s+B$，其中 $?$ 是防止匹配的一个字符。把询问串也这样拼成大串 $Q$，每个询问就是有多少个 $P$ 是 $Q$ 的子串，直接 AC 自动机的复杂度为 $O(|\sum|L)$，其中 $|\sum|$ 是一个 $26$ 的常数。

后者实现比较简单，所以我只完成了第二个算法。