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

Mr_罗 · 2025-11-01 22:22:04 · 题解

首先把每对串分成「LCP + ? + LCS」 的形式，注意判掉 s_1=s_2 和 |t_1|\not=|t_2| 。

我们想要对每个 t 的 ? 找有多少 s 满足：

1. ? 完全相同。

第一条哈希排序一下就好了，时间复杂度 \mathcal O(n\log n)。

第二条有两种处理方法：

::::info[法一] 可以把 s,t 都变成「LCP + # + LCS」，然后就是 AC 自动机板子题了。

注意普通 AC 自动机因为有算重的可能性，需要跳 fail 清标记，但这里不可能算重，所以只要预处理的时候加上对应 fail 的个数就好了。

这部分时间复杂度线性。 ::::

::::info[法二] 对 s 的 LCP 反串和 LCS 分别建 Trie，t 要查询自己祖先公共多少对。考虑两棵 Trie 的 dfs 序构成的平面，一对 s 罩着两个子树对应一个矩形，查询 t 对应一个点，这样就是二维数点了。

这部分时间复杂度一只老哥。 ::::

代码（法一）等公示。