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

tcqwq · 2025-11-01 18:47:36 · 题解

纯度 Trie 做法。比去年 T3 难好多啊。

Solution

定义“替换部分”为 \bold{s_1} 和 \bold{s_2} 第一个字符不同的位置到最后一个字符不同的位置形成的两个子串。例如 \texttt{abcdef} 和 \texttt{accddf} 的替换部分为 \texttt{bcde},\texttt{ccdd}。

我们有这样的性质：

• 如果问询 (\bold{t_1},\bold{t_2}) 得到了二元组 (\bold{s_1},\bold{s_2}) 的贡献，那么这两组字符串的替换部分完全相等。

除了替换部分的要求以外，还要有 \bold{s_1} 是 \bold{t_1} 的子串，才能产生贡献。

所以考虑按照替换部分分类。给替换部分做映射可以用 map<pair<ull,ull>,int>，其中两个 ull 是哈希值。

对于每种替换部分，我们都需要维护下面的内容。

可以把 \bold{s_1},\bold{t_1} 从替换部分劈开，都变为两个部分，记为 sl,sr 和 tl,tr。我们要计数的是，sl 是 tl 的后缀，sr 是 tr 的前缀的字符串个数。

不妨把 sl 和 tl 同时反转，也转换为前缀限制，用 Trie 维护。

把每个 sl 插入到一颗 Trie 中，在 sl 对应的节点上，我们挂一个标记为 sr。那么每次查询就是求 tl 对应节点的根链上，是 tr 的前缀的标记个数。
找对应节点可以直接在 Trie 上跳。如果后继节点为空立刻终止即可。

前缀查询是不好做的，考虑转换为相等。由于 L \le 5 \times 10^6，将查询的 tr 直接拆成 |tr|+1（因为要算上空串）个前缀，对于每个前缀，我们都做一次根链计数即可。

那么我们已经把原问题砍成了这样：

给出一颗树，每个点上挂有若干个点权。多组问询，每次给出一个数和一个点，查询这个点到根的链上，这个数在所有点权中出现了几次。

这可以用 dfs 桶。具体地，离线在 Trie 上跑 dfs，对于点 u，在全局的桶上更新 u 上的所有点权，然后回答 u 节点的问询，递归子树，最后删去 u 上的所有点权。这样我们可以保证，回答问询时桶里面存的就是根链信息。

具体实现大概长这样：

void dfs(int u){
    for(int i = 0;i < w[u].size();i++) cnt[w[u][i]]++;
    for(int i = 0;i < q[u].size();i++) // 回答问询
    // 递归子树
    for(int i = 0;i < w[u].size();i++) cnt[w[u][i]]--;
}

是线性的。

为了让点权变小，还需要把 sr 和 tr 的哈希值离散化。

::::info[做法总结]

• 求出每一对 (\bold{s_1},\bold{s_2}) 的替换部分，并对于每种替换部分建 Trie。
• 拆出 \bold{s_1} 删掉替换部分的前后两个部分 sl,sr 并将 sl 反转。
• 把所有 sl 插入到对应替换部分的 Trie，把所有 sr 的哈希值离散化，并在插入 sl 时顺手挂到节点上。
• 求出每一对 (\bold{t_1},\bold{t_2}) 的替换部分，并判断这对替换部分有没有出现过。
• 拆出 \bold{t_1} 删掉替换部分的前后两个部分 tl,tr 并将 tl 反转。
• 找到 (\bold{t_1},\bold{t_2}) 替换部分的那颗 Trie 中，tl 的对应位置 u。
• 对于 tr 的所有前缀，在 u 上挂上查询。
• 对于每颗 Trie 树使用 dfs 桶解决询问。

时间复杂度和空间复杂度均为 O(L \log L + LA)，其中 A=26。

Code

赛时代码。写的比较杂乱见谅ww。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define B 71
#define N 200209
#define M 5000509
int n,m,typ,len,K[N],ans[N],cnt[M];
ull H[N],HX[M];
string S[N],s1,s2;
map<pair<ull,ull>,int> mp;
struct query{ int num,id; };
struct Trie{
    int V;
    struct node{
        int son[27];
        vector<int> w;
        vector<query> q;
        node(){
            memset(son,0,sizeof(son));
            w.clear(); q.clear();
        }
    };
    vector<node> tr;
    Trie(){
        tr.emplace_back();
        tr.emplace_back();
        tr.emplace_back();
        V = 1;
    }
    inline void ins(int idx,int pre){
        // cout<<"ID "<<idx<<"  "<<"Hash "<<pre<<endl;
        int u = 1;
        for(int i = 0;i < S[idx].size();i++){
            int c = S[idx][i] - 'a' + 1;
            if(!tr[u].son[c]){
                tr.emplace_back();
                tr[u].son[c] = ++V;
            }
            u = tr[u].son[c];
        }
        tr[u].w.emplace_back(pre);
    }
    inline int find(int l){
        int u = 1;
        for(int i = l - 1;i >= 0;i--){
            int c = s1[i] - 'a' + 1;
            if(!tr[u].son[c]) return u;
            u = tr[u].son[c];
        }
        return u;
    }
    inline void dfs(int u){
        for(int i = 0;i < tr[u].w.size();i++) cnt[tr[u].w[i]]++;
        for(int i = 0;i < tr[u].q.size();i++) ans[tr[u].q[i].id] += cnt[tr[u].q[i].num];
        for(int i = 1;i <= 26;i++)
            if(tr[u].son[i]) dfs(tr[u].son[i]);
        for(int i = 0;i < tr[u].w.size();i++) cnt[tr[u].w[i]]--;
    }
} T[N];
inline ull F1(int l,int r){
    ull h = 0;
    for(int i = l;i <= r;i++) h = h * B + (s1[i] - 'a' + 1);
    return h;
}
inline ull F2(int l,int r){
    ull h = 0;
    for(int i = l;i <= r;i++) h = h * B + (s2[i] - 'a' + 1);
    return h;
}
inline void work(){
    cin>>n>>m;
    int tmp = n;
    n = 0;
    H[++len] = 0;
    for(int i = 1;i <= tmp;i++){
        cin>>s1>>s2;
        if(s1 == s2) continue;
        int l = 1e9,r = 0;
        for(int j = 0;j < s1.size();j++)
            if(s1[j] != s2[j]) l = min(l,j),r = max(r,j);
        int u = 0;
        ull res1 = F1(l,r),res2 = F2(l,r);
        if(!mp.count(make_pair(res1,res2)))
            mp[make_pair(res1,res2)] = ++typ;
        u = mp[make_pair(res1,res2)];

        ull h = 0;
        for(int j = r + 1;j < s1.size();j++){
            h = h * B + (s1[j] - 'a' + 1);
            HX[++len] = h;
        }
        n++;
        H[n] = h; S[n] = s1.substr(0,l); K[n] = u;
        reverse(S[n].begin(),S[n].end());
        // cout<<H[n]<<" "<<S[n]<<" "<<K[n]<<endl;
    }
    sort(HX + 1,HX + len + 1);
    len = unique(HX + 1,HX + len + 1) - HX - 1;
    for(int i = 1;i <= n;i++) T[K[i]].ins(i,lower_bound(HX + 1,HX + len + 1,H[i]) - HX);

    for(int i = 1;i <= m;i++){
        cin>>s1>>s2;
        if(s1.size() != s2.size()) continue;
        int l = 1e9,r = 0;
        for(int j = 0;j < s1.size();j++)
            if(s1[j] != s2[j]) l = min(l,j),r = max(r,j);
        ull res1 = F1(l,r),res2 = F2(l,r);
        int idx = mp[make_pair(res1,res2)];
        if(!idx) continue;
        int u = T[idx].find(l);
        ull h = 0;
        T[idx].tr[u].q.emplace_back((query){1,i});
        for(int j = r + 1;j < s1.size();j++){
            h = h * B + (s1[j] - 'a' + 1);
            int tmp = lower_bound(HX + 1,HX + len + 1,h) - HX;
            if(HX[tmp] == h) T[idx].tr[u].q.emplace_back((query){tmp,i});
        }
    }
    for(int i = 1;i <= typ;i++) T[i].dfs(1);
    for(int i = 1;i <= m;i++) cout<<ans[i]<<"\n";
}
signed main(){
    //freopen("replace.in","r",stdin); 
    //freopen("replace.out","w",stdout);
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);
    work();
}

::::

真的很用心写了这篇题解。点个赞呗qwq。

Updates

26/09/17：进行了一部分重写。希望能浅显易懂一点。（）