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

strcmp · 2025-11-01 23:02:46 · 题解

考虑 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。