谐音替换 时空严格线性 题解

its_mygo · 2025-11-02 13:40:02 · 题解

时间复杂度 O(L)，空间复杂度 O(|\Sigma|+L) 的确定性做法。

取出中间不一样的部分，其一样的模式串与询问串之间才可能有贡献。将其建 Trie 树即可。

关于线性建 Trie 树：离线处理，每个节点扫一遍经过其的所有串，对每个字符开一个 vector，并将每个串放入对应的 vector 中，最后再对用到的 vector 进行递归，时间复杂度即可做到与 |\Sigma| 无关。

对于中间部分一样的串，将其前后缀建 Trie 树（方法同上），每个询问要求在第一棵树上是 u 祖先且第二棵树上是 v 祖先的模式串的个数。对第一棵树 dfs 扫描，需要在第二棵树上单点修改，查询根到某结点的权值和。注意到所有查询结点的深度和为 O(L)，暴力即可。