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

pig1121 · 2025-11-02 07:05:54 · 题解

这个唐诗被题面和 B 性质误导，认为可能有多个匹配位置，又认为 AC 自动机不可过，获得了 0pts 的好成绩，你也来试试吧。

AC自动机。

赛后显然注意到每组 s 在每个 t 上只有一个贡献位置（要求除匹配位置外相等，故 s_0,s_1 在去除 LCP、LCS 后应于 t_0,t_1 去除 LCP、LCS 后相等）。

我们直接定义两个字符串二元组相等当且仅当 s_{0,i}\times|\Sigma|+s_{1,i}=t_{0,i}\times|\Sigma|+t_{1,i}，用这个定义对 s 建立 AC 自动机，拿 t 在上面匹配，字符集为 676，主席树显然卡不过去（说不定暴力跳 fail 然后记忆化可以水过）。

然后我们发现问题是这么做字符集太大了，而AC自动机在保证字符集大小时复杂度只依赖于左、右端点的单调性，所以我们对 s_0,s_1 分别建立 AC 自动机，匹配时同时在两个自动机上匹配对应串，由于 border 具有传递性，保证当前匹配的点长度相同即可……

吗？

注意到这样可能会导致两个点状态不一样，所以还要求一次并，是假的。

尝试结合这两个做法，将两次匹配放在同一个自动机上，但是不是同时而是先后进行。具体地，对做法1中的一条转移边 p\rarr son_p(i,j)，将其拆解为两条边 p\rarr son_p(i),son_p(i)\rarr son_{son_p(i)}(j)，字符集减小到 26，长度翻倍，复杂度除掉一个 |\Sigma|。

匹配时注意不能在拆出来的节点计算贡献。

时空复杂度 O(\sum len\times|\Sigma|)。

这个做法貌似和直接插 \overline{s_{0,i}s_{1,i}...s_{0,n}s_{1,n}} 一样?

题外话：原本是想用可持久化分块维护做法 1 的 son 数组，感觉会炸空间，然后发现这个根号正好等价于把转移分成两层……