题解：P14363 [CSP-S 2025] 谐音替换 / replace（暂无数据）

· · 题解

[CSP-S 2025] T3 谐音替换 题解

先特判掉 |t_1|\neq|t_2| 的情况，答案为 0。

然后对于每个输入的 s_1,s_2，设 l 为最小的满足 s_1[l]\neq s_2[l] 的下标，r 为最大的满足 s_1[r]\neq s_2[r] 的下标，若 s_1=s_2 则令 l=|s_1|,r=|s_1|-1，然后设

f_0(s_1,s_2)=s_1[l,r]+s_2[l,r] f_1(s_1,s_2)=\text{reverse}(s_1[0,l-1]) f_2(s_1,s_2)=s_2[r+1,|s_1|-1]

那么显然有

ans_i=\sum\limits_{j=1}^n[f_0(s_{j,1},s_{j,2})=f_0(t_{i,1},t_{i,2})][f_1(s_{j,1},s_{j,2})\in \text{prefix}(f_1(t_{i,1},t_{i,2}))][f_2(s_{j,1},s_{j,2})\in \text{prefix}(f_2(t_{i,1},t_{i,2}))]

其中 \text{prefix}(s) 表示 s 的所有前缀构成的集合。

然后，因为 f_0 不同的 s,t 之间肯定没有贡献，可以首先按照 f_0 的哈希值用 map 分类，每一个类都独立。

对于每一个 f_0 相同的类，要求 s 的 f_1,f_2 都是 t 的前缀，而前缀关系等价于 Trie 树上的祖先关系，所以如果把每种哈希值的 f_1,f_2 都各开一个 Trie，那么等价于在 f_0 对应的两个树上，f_1(s) 是 f_1(t) 的祖先，且 f_2(s) 是 f_2(t) 的祖先。

然后对 Trie 树求出 dfs 序，设点 x 的 dfs 序为 dfn[x]，x 子树内最大的 dfn 为 dfm[x]，那么一个 s,t 在 Trie 上对应的两个点对 (x_1,x_2),(y_1,y_2) 需要满足 dfn[y_1]\in[dfn[x_1],dfm[x_1]],dfn[y_2]\in[dfn[x_2],dfm[x_2]] 。

至此就是二维矩形加、单点查询了，使用二维差分容易转化为单点加、二维矩形查询，扫描线+树状数组即可。

时间复杂度 O((L_1+L_2)|\Sigma|+(n+q)\log(L_1+L_2))。

::::warning[注意事项] 不要使用 map<string,int>，哈希不要模 1e9 级别模数。内存都给 2GB 了应该不会爆吧。

查询串在 Trie 树上往下跳的时候，如果当前节点不存在对应字母的子节点，则代表查询串只有这个前缀是有效的，后面都匹配不上了，务必立即 return。否则如果后面再出现有子节点的字母，则还会继续跳，这个时候跳出来的就不是前缀了，然后就WA了，100\to rand(0,100)。 ::::

::::success[代码]

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ve vector<int>
#define mid (l+r>>1)
#define lx (x<<1)
#define rx (x<<1|1)
using namespace std;
const int N=1e6+2,M=6e6+2;
const ll P=1e16+61;
int n,m,k,d,ck,cnt,tr[M],dfn[M],ans[N],dfm[M],rt[N],f[M][26];
pii c[N];
struct node{int x,y,z,t;}mf[N];
map<ll,int>mp;
void mdf(int x,int y){for(;x<=k;x+=x&-x)tr[x]+=y;}
int qry(int x,int y=0){for(;x;x-=x&-x)y+=tr[x];return y;}
ll hs(const string&s){
    ll h=0;
    for(char i:s)h=(h*127+i-95)%P;
    return h;
}
int add(int x,const string&s){
    for(char i:s){
        if(!f[x][i-97])f[x][i-97]=++k;
        x=f[x][i-97];
    }
    return x;
}
int find(int x,const string&s){
    for(char i:s)
        if(f[x][i-97])x=f[x][i-97];
        else return x;//这一行如果不加会随机得分
    return x;
}
void dfs(int x){
    dfn[x]=++ck;
    for(int i=0;i<26;i++)
        if(f[x][i])dfs(f[x][i]);
    dfm[x]=ck;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s1,s2,t0,t1,t2;
        cin>>s1>>s2;
        int l=0,r=s1.size()-1;
        while(l<s1.size()&&s1[l]==s2[l])t1+=s1[l++];
        while(r>l&&s1[r]==s2[r])t2+=s1[r--];
        for(int j=l;j<=r;j++)t0+=s1[j],t0+=s2[j];
        reverse(t1.begin(),t1.end());
        reverse(t2.begin(),t2.end());
        ll h=hs(t0);
        int&z=mp[h];
        if(!z)rt[z=++d]=++k,rt[++d]=++k;
        c[i]={add(rt[z],t1),add(rt[z+1],t2)};
    }
    for(int i=1;i<=d;i++)dfs(rt[i]);
    for(int i=1;i<=n;i++)
        mf[++cnt]={dfn[c[i].fi],dfn[c[i].se],1,0},
        mf[++cnt]={dfn[c[i].fi],dfm[c[i].se]+1,-1,0},
        mf[++cnt]={dfm[c[i].fi]+1,dfn[c[i].se],-1,0},
        mf[++cnt]={dfm[c[i].fi]+1,dfm[c[i].se]+1,1,0};
    for(int i=1;i<=m;i++){
        string s1,s2,t0,t1,t2;
        cin>>s1>>s2;
        if(s1.size()!=s2.size())continue;
        int l=0,r=s1.size()-1;
        while(l<s1.size()&&s1[l]==s2[l])t1+=s1[l++];
        while(r>l&&s1[r]==s2[r])t2+=s1[r--];
        for(int j=l;j<=r;j++)t0+=s1[j],t0+=s2[j];
        reverse(t1.begin(),t1.end());
        reverse(t2.begin(),t2.end());
        ll h=hs(t0);
        if(!mp.count(h))continue;
        int z=mp[h];
        mf[++cnt]={dfn[find(rt[z],t1)],dfn[find(rt[z+1],t2)],i,1};
    }
    sort(mf+1,mf+cnt+1,[](node x,node y){
        return x.x!=y.x?x.x<y.x:x.t<y.t;
    });
    for(int i=1;i<=cnt;i++)
        if(mf[i].t)ans[mf[i].z]=qry(mf[i].y);
        else mdf(mf[i].y,mf[i].z);
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    return 0;
}

::::