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

· · 题解

Trie+Hash 简单线性做法

考虑将每个替换抽象成一个四元组 (L_s,X_s,Y_s,R_s) ：

其中 X_s 与 Y_s 为 s_{i,1} 与 s_{i,2} 极长不同的子串 ， L_s 为极长相同的前缀 ， R_s 为极长相同的后缀 。

对于每一个询问 t 我们也可以类似地定义四元组 (L_t,X_t,Y_t,R_t) 。

我们很容易发现一个合法的替换满足如下四个条件：

  3. X_s=X_t
  4. Y_s=Y_t

考虑继续转换为三个限制条件：

  3. \left| X_s \right| = \left| X_t \right|

正确性可以证明

其中后缀限制进行翻转后可以变为前缀限制

对于第二个限制，我们用 Y_s+R_s 的哈希值表示这个串。

对于第三个限制，我们把每个长度随机赋权，并把长度对应权值乘进 Y_s+R_s 的哈希值后挂在树上。

这样我们的每一次查询的流程如下：

  1. 先找出 L_t+X_t 长度大于等于 \left| X_s \right| 的后缀在字典树上对应的路径
  2. 枚举 Y_t+R_t 长度大于等于 \left| X_s \right| 的前缀，在树上路径查询。

如果在线做可以用主席树做到 O(L\log n)

如果离线下来，让每个字典树的节点找到他可以贡献的询问一起做，复杂度就是线性的。

1.4K代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define left wshnl
#define right wkqnl
using namespace std;
const int N=200005;
const int M=5e6+5; 
mt19937_64 rnd(time(0));
int n,q,ans[N];ull w[M];
int ch[M][30],trie=1;
ull base=131;
vector<ull>add[M];
struct event{
    int u,op;ull tm;
};
vector<event>e[M];
unordered_map<ull,int>cnt;
void dfs(int u){
    for(auto i:add[u])cnt[i]++;
    for(auto i:e[u])ans[i.u]+=i.op*cnt[i.tm];
    for(int i=0;i<26;i++)if(ch[u][i])dfs(ch[u][i]);
    for(auto i:add[u])cnt[i]--;
}
int main(){
    for(int i=1;i<M;i++)w[i]=rnd();
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        string x,y;cin>>x>>y;
        int l,r;
        for(l=0;l<x.size()&&x[l]==y[l];l++);
        for(r=x.size()-1;r>=0&&x[r]==y[r];r--);
        int u,k;
        for(u=1,k=r;k>=0;u=ch[u][x[k]-'a'],k--){
            if(!ch[u][x[k]-'a'])ch[u][x[k]-'a']=++trie;
        }
        ull H=0;
        for(int j=l;j<x.size();j++)H=H*base+y[j];
        H*=w[r-l+1];
        add[u].push_back(H);
    }
    for(int i=1;i<=q;i++){
        string x,y;cin>>x>>y;
        if(x.size()!=y.size())continue;
        int l,r;
        for(l=0;l<x.size()&&x[l]==y[l];l++);
        for(r=x.size()-1;r>=0&&x[r]==y[r];r--);
        int u,v=1,k;
        for(u=1,k=r;k>=0&&ch[u][x[k]-'a'];u=ch[u][x[k]-'a'],k--)if(k>=l)v=u;
        if(k>=l)continue;
        ull H=0;int ans=0;
        for(int j=l;j<x.size();j++){
            H=H*base+y[j];
            if(j<r)continue;
            e[u].push_back((event){i,1,H*w[r-l+1]});
            e[v].push_back((event){i,-1,H*w[r-l+1]});
        }   
    }
    dfs(1);
    for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
    return 0;
}