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

考虑 $s_1$ 和 $s_2$ 的 LCP 和 LCS 夹在中间的那一块。

比如考虑 $s_1 = x + y + z$ 和 $s_2 = x + y' + z$。

并且令 $t_1 = a + b + c$ 和 $t_2 = a + b' + c$。

令 $x$ 是 $a$ 的后缀，$z$ 是 $c$ 的前缀，$y = b$ 且 $y' = b'$。

按 $y$ 或者 $y'$ 分组，建立若干字典树数点即可，前后缀关系可以类似我们的树状数组数点，这是两个 dfn 序区间，变成了矩形加单点查，是经典扫描线问题。

复杂度 $\Theta(|L| \times |\Sigma| + (n + q) \log |L|)$。

实际上不需要 ACAM。