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

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$ 数组，感觉会炸空间，然后发现这个根号正好等价于把转移分成两层……