题解：P14363 [CSP-S 2025] 谐音替换 / replace

· · 题解

首先判掉 |t_1|\neq|t_2|，题意即找到 t_1 匹配 s_1 的位置且换为 s_2 后变为 t_2。

使用 acam 刻画第一个匹配，先对 s_1 构建 acam 并记录每个点对应的 s_2 和 fail 树，询问时枚举替换的最后一个位置 p，设 t_{1,1},\dots,t_{1,p} 对应 acam 中 u，则相当于把一段后缀换为 fail 树上 u 到根路径上对应的某个 s_2。

使用哈希刻画第二个匹配，只需考虑 s_1,s_2 及 t_1,t_2 的哈希值的差，不难转化为树上每个点有若干点权，求某点到根路径上某点权出现次数，离线后 dfs 顺便 umap 维护即可。

时间复杂度 O(n+q+L|\Sigma|)。

如果你两边都用 acam 刻画容易得到一个二维数点做法。

下面给出考后复现的代码：

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l),qwp=(r);i<=qwp;i++)
#define per(i,r,l) for(int i=(r),qwp=(l);i>=qwp;i--)
#define pb push_back
#define ins insert
#define umap unordered_map
using namespace std;
namespace ax_by_c{
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<pll,int> ND;
constexpr ll M1=1e9+9;
constexpr ll M2=1145141;
constexpr ll B1=131;
constexpr ll B2=1331;
constexpr int L=5e6+5;
constexpr int S=26;
constexpr int QQQ=2e5+5;
inline int frint(){int n=0;char c=getchar();while(c<'0'||'9'<c)c=getchar();while('0'<=c&&c<='9')n=n*10+c-48,c=getchar();return n;}
inline void wrll(ll x){if(x>9)wrll(x/10);putchar(x%10+48);}
inline pll ext(pll x,char y){return {(x.first*B1+y)%M1,(x.second*B2+y)%M2};}
inline pll operator - (pll x,pll y){return {(x.first-y.first+M1)%M1,(x.second-y.second+M2)%M2};}
inline ll H(pll x){return x.first*M2+x.second;}
int n,m,q;char s[L],ss[L];
inline void rd(char *qwq){m=0;char c=getchar();while(c<'a'||'z'<c)c=getchar();while('a'<=c&&c<='z')qwq[++m]=c,c=getchar();}
int son[L][S],idx;vector<pll>hs[L];
int _ins(){int u=0;rep(i,1,m){int &v=son[u][s[i]-'a'];if(!v)v=++idx;u=v;}return u;}
int kmp[L],nxt[L][S];queue<int>Q;
struct LSTNODE{int v,nxt;}g_[L];
int gc_,ghd_[L];
inline void add(int x,int y){g_[++gc_]={y,ghd_[x]},ghd_[x]=gc_;}
void bld(){
    rep(i,0,25)if(son[0][i])nxt[0][i]=son[0][i],Q.push(son[0][i]);
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        rep(i,0,25)nxt[u][i]=((son[u][i])?(son[u][i]):(nxt[kmp[u]][i]));
        rep(i,0,25){int v=son[u][i];if(!v)continue;kmp[v]=nxt[kmp[u]][i],Q.push(v);}
    }
    rep(i,1,idx)add(kmp[i],i);
}
vector<ND>qs[L];ll ans[QQQ];umap<ll,int>hcnt;
void dfs(int u){
    for(auto it:hs[u])hcnt[H(it)]++;
    for(auto it:qs[u])if(hcnt.count(H(it.first)))ans[it.second]+=hcnt[H(it.first)];
    for(int i=ghd_[u];i;i=g_[i].nxt)dfs(g_[i].v);
    for(auto it:hs[u])if(!(--hcnt[H(it)]))hcnt.erase(hcnt.find(H(it)));
}
void main(){
    n=frint(),q=frint();
    rep(_,1,n){
        rd(s);pll h1={0,0};rep(i,1,m)h1=ext(h1,s[i]);int pos=_ins();
        rd(s);pll h2={0,0};rep(i,1,m)h2=ext(h2,s[i]);hs[pos].pb(h2-h1);
    }
    bld();
    rep(_,1,q){
        rd(s);int tm=m;rd(ss);if(tm!=m)continue;
        int pp=m;while(pp>1&&s[pp]==ss[pp])pp--;
        int u=0;pll h1={0,0},h2={0,0};
        rep(i,1,m){
            u=nxt[u][s[i]-'a'],h1=ext(h1,s[i]),h2=ext(h2,ss[i]);
            if(pp<=i)qs[u].pb({h2-h1,_});
        }
    }
    dfs(0);
    rep(i,1,q)wrll(ans[i]),putchar('\n');
}
}
int main(){
    // freopen("replace.in","r",stdin);
    // freopen("replace.out","w",stdout);
    ax_by_c::main();
    return 0;
}
/*
g++ -std=c++14 -O2 -Wall -Wextra "-Wl,--stack=2048000000" A.cpp -o A.exe
A.exe
*/