纯度 ACAM

怎么一堆大佬写了题解，算了看见队爷假装没看见。

温馨提示：题目要求只能替换一次。注意到每个 $(s_{i,1},s_{i,2})$ 实际上的替换是把除了它两端的相同字符以外的中间那一部分，因为两端的字符替换了等于没替换。而每个 $(t_{i,1},t_{i,2})$ 其实是需要一个 $s$ 二元组使自己两端极长相同子段外的中间部分恰好被替换掉，因此要求 $s$ 和 $t$ 二者中间的核心部分相同。同时也需要符合替换条件，也就是 $s$ 替换的部分放进 $t$ 串里两端多余的部分是恰好匹配的。

这启发我们像 P9196 一样重构串。首先中间核心部分是匹配关键，由于 $s_{i,1}=s_{i,2}$ 其长度恰好是 $s$ 串单个的两倍，具有单一性，直接两端加上特殊字符，剩下部分贴在特殊字符两旁用于匹配，即拆分 $(s_{i,1},s_{i,2})$ 和 $(t_{i,1},t_{i,2})$ 二元组为字符串 $\text{A?BD?C}$，其中 $\text{?}$ 为特殊字符，两串分别为 $\text{ABC}$ 和 $\text{ADC}$，$\text{A}$ 和 $\text{C}$ 分别为两个串的最长公共前后缀。

用 ACAM 跑多模匹配即可，由于每个 $s$ 最多在每个 $t$ 中出现一次，出现至少一次的 $s$ 串数量等于所有 $s$ 串的出现次数，可以通过对 fail 进行前缀和规避暴力跳，这样我们在所匹配的这个节点即可直接计算贡献。

时间复杂度 $O(|\sum|L_1+L_2)$

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,q[10000005],l,r,ans,tot;
char k[10000005],k1[5000005],k2[5000005];
int ch[10000005][27],fail[10000005],num[10000005];
#define ca (k[i]-'a')
#define v (ch[u][i])
void trie(int s){
    int u=0,l=strlen(k);
    for(int i=0;i<l;u=ch[u][ca],++i)if(!ch[u][ca])ch[u][ca]=++cnt;
    num[u]++;
}
void build(){
    for(int i=0;i<27;++i)if(ch[0][i])fail[ch[0][i]]=0,q[++r]=ch[0][i];
    while(l<r){
        int u=q[++l];num[u]+=num[fail[u]];
        for(int i=0;i<27;++i)
            if(v)fail[v]=ch[fail[u]][i],q[++r]=v;
            else ch[u][i]=ch[fail[u]][i];
    }
}
void mccz(){
    int u=0,l=strlen(k);
    for(int i=0;i<l;++i)u=ch[u][ca],ans+=num[u];
}
inline int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
inline void write(int x){
    x<0?x=-x,putchar_unlocked('-'):0;static short st[10],top(0);
    do st[++top]=x%10,x/=10;while(x);
    while(top)putchar_unlocked(st[top--]|48);
}
inline void getst(int i){
    int l=strlen(k1),j,f,p,tot=-1;
    for(j=0;j<l;++j){if(k1[j]==k2[j])k[++tot]=k1[j];else break;}
    for(f=l-1;~f;--f)if(k1[f]!=k2[f])break;
    k[++tot]='{';
    for(p=j;p<=f;++p)k[++tot]=k1[p];
    for(p=j;p<=f;++p)k[++tot]=k2[p];
    k[++tot]='{';
    for(p=f+1;p<l;++p)k[++tot]=k2[p];
    k[++tot]='\0';
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)scanf("%s",k1),scanf("%s",k2),getst(i),trie(i);
    build();
    for(int i=1;i<=m;++i){
        scanf("%s",k1),scanf("%s",k2),ans=0;
        if(strlen(k1)==strlen(k2))getst(i),mccz();
        write(ans),putchar_unlocked('\n');
    }
	return 0;
}