谐音替换新做法！

Moya_Rao · 2026-09-23 21:28:26 · 题解

前言

我爸在魔法学院群里，听到石老师分享了一个新做法，然后我~~通过将线索扔给 AI~~ 拼出一个完整的做法。目前我是没有在题解区看到相同或类似的做法，所以我就来写一波题解 > <。求过喵喵谢谢喵。

这个方法，我个人认为还是比其他做法要简单的（骗你的其实其他做法我根本看不懂），没有用到任何高难度的算法，思维也没有很复杂，中间有几个小结论但都是比较好证的，做法比较巧妙喵。

本文较长，耗时较久，希望你能耐心看完喵 /xin。

思路

首先，我们发现这个替换不是“绝对性”的。也就是说，这个替换会有兀余的成分，比如说将 aca 替换为 aba 中，最前面的一个 a 和最后面的一个 a 是两串均有的，这里的本质是将一个 c 换成 b。但也不能把前后缀直接删掉，因为前后缀限制了中间核心部分左右的状况。询问其实也是这样，也有一个中间核心被替换的部分，两边也可能有一些兀余成分（两个串都相等）。

因此，我们考虑先把替换和询问都拆成四个部分 st,ed,mid_1,mid_2，其中 st 和 ed 为两串共有的前后兀余部分（没有兀余部分即为空串），而 mid_1 和 mid_2 就是中间从 mid_1 替换为 mid_2 的核心部分。显然，根据我们上面的设定，mid_1 和 mid_2 的第一个字符一定不相同，最后一个字符也一定不相同。

接下来就有第一个结论：只有核心替换部分的二元组 (mid_1,mid_2) 完全相等的替换和询问，才可能用这种替换去处理这个询问（后称为“能匹配上”）。

这个看起来或许有一些些的不可思议（？），因为完全相等好像太苛刻了……但是确实是这样的，接下来给出简单的证明：

显然，当该替换与询问的核心替换部分的二元组完全相等时，肯定能匹配上，因此仅需证明在不完全相等时无法匹配上。
当替换与询问的核心部分长度一样但内容不同时，肯定无法匹配。
当替换的核心部分长度比询问长时，替换时会影响到询问的非核心部分导致其产生变化，进而无法达到询问的目的，那么也无法匹配。
反之，如果替换的核心部分长度比询问短，替换时询问的一些核心部分就不会产生变化，也无法达到询问目的，不匹配。
综上，只有当其二元组 (mid_1,mid_2) 完全相等时才能匹配。

注意，这个结论说的是可能能替换，这意味着，能匹配上不代表一定能成功解决询问的问题。这是显然的，因为还有前后缀的限制，也需要匹配上。

但是这个结论可以很方便的为我们划分组别，将二元组为一类的替换和询问分为一组，不同的组互不干扰，因此只需要考虑同一组的情况了。

接下来就讲明怎么具体去处理其中的一组。

先思考一个问题：如果目前 (mid_1,mid_2) 已经完全匹配了，其 st 和 ed 要满足什么限制？

显然，要求替换的 st 为询问的 st 的后缀，同理要求替换的 ed 为询问的 ed 的前缀。不要求一定是真后缀和真前缀，也就是可以相等。

一个后缀一个前缀非常烦人，考虑将 st 倒过来处理，这样就都是前缀了。

如果 t 是 s 的前缀，有一个一定满足的、很基本的性质是什么？对啦，t \le s，这里的 \le 指的是按字典序比较。那么，这就启示我们分别将这一组的替换和询问按照其 st 的字典序升序排序。然后枚举每个询问去处理。

然后我先讲一遍处理过程。在讲过程的时候，你可能会对某个部分产生疑惑“为什么能这么干”“这样做为什么是对的”，这些部分我在讲完过程之后会给予证明。当然你也可以自己证掉它，都还简单，相信在座的 dsa 都能很快秒掉吧。

我们枚举每个询问，然后一个指针维护当前考虑了哪些替换。并开一个栈维护当前前缀，即 st，合法的那些替换（合法表示是该询问的前缀），同时用一个 Trie 树维护当前所有合法替换的 ed 的情况（和栈是同步的）。每次处理到一个新的询问，先从上到下（从栈顶到栈底）遍历这个栈，如果当前栈顶对应的替换的 st 已不是当前询问的 st 的前缀，那么直接弹出这个栈顶、从 Trie 中删除并在之后不再考虑它；如果当前栈顶对应的替换的 st 是当前询问的 st 的前缀，停止遍历，栈内还留存的替换也一定是合法的。

此时开始考虑新的替换，因为我们是用指针遍历，所以在枚举到下一个询问时，会出现一些新的替换（新的替换的 st 的字典序一定不能比当前询问的 st 的字典序大）。如果这个新的替换的 st 是当前询问的 st 的前缀，那么就将其压进栈中并加入 Trie 树；如果不是，直接扔开并在之后的处理中不再考虑。

到这里，所有当前 st 合法的替换的 ed 都已经存在 Trie 里面了，这个时候用当前询问的 ed 遍历 Trie 树，并对应统计 ed 也为当前询问的 ed 的替换的个数，并记为答案。Trie 的维护是简单的，在这里就不多说了。

过程讲到这里，想必大家也产生了一些疑惑（？），也许吧，中间有一些很笃定的过程，看起来不太对，但事实上是对的，接下来我一个个剖析。我的证明可能存在不太严谨或兀余的情况，欢迎大家在评论区捉虫喵。

为什么“如果当前栈顶对应的替换的 st 已不是当前询问的 st 的前缀，那么直接弹出这个栈顶、从 Trie 中删除并在之后不再考虑它”？
- 这里只解释最后的“并在之后不再考虑它”是为什么（前面的不至于看不懂吧 OvO）。
- 思考为什么它的 st 不会是当前询问的 st 的前缀了，因为它的字典序较小，那么可以考虑长度：
- 第一种情况，它的 st 的长度不超过当前询问的 st 的长度，说明在只截取两段前“它的 st 的长度”长度的字符串的情况下，其字典序已严格小于当前询问的 st 截取段，那更往后的询问的 st 的截取段只会字典序更大，再也不可能相等了。
- 第二种情况，它的 st 的长度比当前询问的 st 的长度要大，这个时候它显然不是当前询问的 st 的前缀，但是它的 st 的字典序比当前询问的 st 的要小，说明在其中一个位置它的 st 的字母已严格小于当前询问的 st 的字母，而之后的询问的 st 的字典序是大于当前询问的 st 的字典序的，这个位置的字母只会更大，或者在更前面的位就出现更大的现象，也更不可能是后面的串的前缀了。
为什么“如果当前栈顶对应的替换的 st 是当前询问的 st 的前缀，停止遍历，栈内还留存的替换也一定是合法的”？
- 大家产生疑问的肯定也是最后一句话“栈内还留存的替换也一定是合法的”。
- 考虑栈里的 st 有什么性质，因为它们都是前面某个询问的 st 维护好了的前缀，因此从栈底到栈顶，都是一个前缀包含的关系，其中栈内所有的 st 都是栈顶的 st 的前缀。那么如果当前栈顶已经是当前询问的 st 的前缀，那么根据“栈内所有的 st 都是栈顶的 st 的前缀”，栈内其他的元素的 st 一定也是当前询问的 st 的前缀，那就不需要再处理下去了。
为什么“如果不是（当前询问的 st 的前缀），直接扔开并在之后的处理中不再考虑”？
- “扔开”可以理解，但是“在之后的处理中不再考虑”是什么原因呀。
- 你考虑这个还是字典序比当前询问的 st 要小，还是不是前缀，还是之后不再考虑——那么是不是就变成了「1.」的情况？那么直接看那里的证明即可了，我就不再写一遍了 qwq。

那么讲到这里，上面的处理过程部分应该都彻底理解了。如果我某些证明的地方有问题，看不懂的话，也欢迎提问喵。

处理完这个，整到题目就结束了，只剩下一些细节上的处理，比如说最开始分组时用 map 做编号映射然后开 vector 维护、最终的答案存储在 ans 数组里并在 vector 维护询问时加上编号等等。这些实现上的细节不算很难，大家也可以结合我的代码看看喵。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
const int L = 5e6+5;
struct state{
    string st,ed,mid1,mid2;
    //分别表示前后相同缀以及中间的核心替换
};
struct node{
    string st,ed;
    int id;
    //如果是询问，则 id 存储询问编号，用于统计答案
};
int n,Q;
int Cnt_id;//map 编号
map<pair<string,string>,int> mp;
vector<node> c[N],q[N];
//c 表修改 q 表询问
int ans[N];//存储最终的答案 也就是最后要输出的内容
int tr[L][26],f[L],val[L],Cnt;//Trie 维护较多信息
stack<int> stk;//栈 用于存储当前在 Trie 里的一些的信息 是倒着来的
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
state __get(string s1,string s2){
    //对这两个字符串提取 state 所需信息
    state res={"","","",""};
    int len=s1.size();//长度 后面需要用
    int l=0;
    for(;l<len&&s1[l]==s2[l];l++)res.st+=s1[l];//不断累加
    int r=len-1;
    for(;r>=l&&s1[r]==s2[r];r--)res.ed+=s1[r];
    //此时得到的 st 和 ed 都是反的（我哪知道
    //所以都需要 reverse
    reverse(res.st.begin(),res.st.end());
    reverse(res.ed.begin(),res.ed.end());
    for(int i=l;i<=r;i++)
        res.mid1+=s1[i],res.mid2+=s2[i];
        //提取两个中间值
    return res;//返回最终得到的值
}
bool cmp(node d1,node d2){
    return d1.st<d2.st;//按照 st 的字典序排序
}
void init(){
    //清空字典树！！
    for(int i=0;i<=Cnt;i++)
        for(int x=0;x<26;x++)
            tr[i][x]=0,f[i]=0,val[i]=0;
    Cnt=0;return;
}
void Add(string s){
    int now=0;
    for(char ch:s){
        int x=ch-'a';
        if(!tr[now][x])tr[now][x]=++Cnt;
        now=tr[now][x],f[now]++;
    }
    val[now]++;//标记结尾 方便统计答案
    return;
}
void Del(string s){
    int now=0;
    for(char ch:s){
        int x=ch-'a';
        now=tr[now][x],f[now]--;//等价于删除
    }
    val[now]--;//取消结尾标记
    return;
}
int Ask(string s){
    int now=0,cccnt=val[now];
    //注意这里 cccnt 的初值！有空串前后缀的情况！
    for(char ch:s){
        int x=ch-'a';
        if(!tr[now][x])break;
        now=tr[now][x];
        if(!f[now])break;//原来有这个点 但是被删掉了 那就也作废了
        cccnt+=val[now];//只能加结尾标记
    }
    return cccnt;//一路上统计到的答案
}
bool Is_it(const string &s,const string &t){
    //判断 t 是否为 s 的前缀
    if(t.size()>s.size())return 0;//前缀的长度不能比原串长吧
    for(int i=0;i<t.size();i++)
        if(t[i]!=s[i])return 0;//不能有不相同
    return 1;//确实是前缀！
}
int main(){
    n=read(),Q=read();
    for(int i=1;i<=n;i++){
        string s1,s2;cin>>s1>>s2;
        state tmp=__get(s1,s2);
        if(!mp[{tmp.mid1,tmp.mid2}])
            mp[{tmp.mid1,tmp.mid2}]=++Cnt_id;
            //如果之前没有这个类别的询问 就先处理一下
        int id=mp[{tmp.mid1,tmp.mid2}];//得到编号
        c[id].pb({tmp.st,tmp.ed,0});//仅需传参 st 和 ed
    }
    for(int i=1;i<=Q;i++){
        string s1,s2;cin>>s1>>s2;
        state tmp=__get(s1,s2);//前面也是一样的步骤
        int id=mp[{tmp.mid1,tmp.mid2}];
        if(!id)ans[i]=0;//没东西给你改
        else q[id].pb({tmp.st,tmp.ed,i});//否则加入序列中
    }
    for(int x=1;x<=Cnt_id;x++)
        sort(c[x].begin(),c[x].end(),cmp),
        sort(q[x].begin(),q[x].end(),cmp);
        //这个排序应该。不会。T 吧。
    //cout<<Cnt_id<<"!!!\n";
    for(int x=1;x<=Cnt_id;x++){
        if(q[x].empty())continue;//没询问你玩个啥
        init();//先把字典树清空 还原
        while(!stk.empty())stk.pop();//栈也要清空
        int len=c[x].size();
        int now=0;//当前考虑到第 now 个操作，0~now-1 的已经处理完毕
        for(auto u:q[x]){
            //先是枚举每个询问 然后对应考虑操作
            while(!stk.empty()){
                int pos=stk.top();
                if(Is_it(u.st,c[x][pos].st))break;//满足条件了
                Del(c[x][pos].ed);//从 Trie 里面删掉
                stk.pop();//从栈里面弄出去
            }
            //考虑加入新的
            while(now<len&&c[x][now].st<=u.st){//没越界
                if(Is_it(u.st,c[x][now].st))//如果它们的前缀满足包含关系
                    Add(c[x][now].ed),//那么就可以把操作的后缀塞进 Trie
                    stk.push(now);//加入栈等待之后的制裁
                now++;//不管是否加成功了 都要往后移动
            }
            //这个时候我们所有的东西都维护好了
            //然后就是一个答案的查询
            ans[u.id]=Ask(u.ed);//把当前查询的后缀去字典树里跑 然后统计个数
        }
    }
    for(int i=1;i<=Q;i++)cout<<ans[i]<<"\n";//输出
    return 0;
}
/*
2 1
xabcx xadex
bc de
xabcx xadex
*/

::::

然后这里再提到一个东西，时间复杂度。我们这个做法，你仔细去算它的时间复杂度，大概是 O(L \log L) 的（n 的维度因为比 L 小我就忽略掉了），但是有较大的常数，~~尤其因为我人傻常数大~~，所以很容易 TLE。这个时候，我们发现代码中有一个判断一个字符串是否为另一个字符串的前缀的函数：

bool Is_it(string s,string t){
    //判断 t 是否为 s 的前缀
    if(t.size()>s.size())return 0;//前缀的长度不能比原串长吧
    for(int i=0;i<t.size();i++)
        if(t[i]!=s[i])return 0;//不能有不相同
    return 1;//确实是前缀！
}

注意传参那个部分，是直接开的 string，这导致在每次调用该函数时都会额外开辟一块临时空间存储当前的 s 和 t，且会将其拷贝一遍，这样会让时间复杂度翻倍。而我们在处理的过程中，这个函数的调用频率是最高的，它甚至可以说是时间复杂度的“主要贡献者”，这样大的常数让我们无法接受。

怎么办呢？简单，我们把传参中 string 改成 const string& 即可。这样不仅是取了原值地址（确保不额外开辟空间并拷贝字符串浪费时间），const 能确保不对原字符串做修改，能大大加快效率。

因此最后，在我的代码里是这样写的：

bool Is_it(const string &s,const string &t){
    //判断 t 是否为 s 的前缀
    if(t.size()>s.size())return 0;//前缀的长度不能比原串长吧
    for(int i=0;i<t.size();i++)
        if(t[i]!=s[i])return 0;//不能有不相同
    return 1;//确实是前缀！
}

这样真的要快多了！！

后记

写完了，累死我了喵。这篇题解比较长，如果你坚持看到了这里，麻烦留个赞喵 /xin。

这个做法还是比较厉害的，虽然说中间用到的结论都比较简单，但在真正的思考过程中能直接猜到这个结论并证出来还是有一定难度的。整个思路并不难，但是中间的思维部分，我认为是很巧妙的。

以及再次感谢石老师提供了这个新做法喵！

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！