题解：P13960 [ICPC 2023 Nanjing R] 后缀结构

Larunatrecy · 2026-07-20 21:06:12 · 题解

首先 O(nm) 的暴力是简单的，我们建立 AC 自动机，那么 f(i,j) 实际上就是在 AC 自动机上跑字符串 s_i+t_j 最后到达的结点的深度。

因此问题等价于，初始时所有节点上都有一个棋子，进行 m 次移动，每次所有棋子沿着 t_i 边移动（不存在就跳 fail），求每次移动后所有结点的深度和。

对于一个结点 u，求出 k 表示 k 次移动后结点 i 第一次需要跳 fail，设跳 fail 跳到的结点是 v，分类讨论一下：

• 如果 d_v\geq k，设 w 为 v 的 k 级祖先，那么从 u 出发和从 w 出发，k 步之后到的点是一样的，k 步之前因为都是向下走，所以对答案的贡献都是一个公差为 1 的等差数列，我们可以弥修正以下这两个贡献的差，然后把从 u 出发的看作是从 w 出发的，注意显然有 d_w<d_u。
• 如果 d_v<k，那么可以发现从 u 出发和从根节点 0 出发，k 步之后到的点是一样的（这是因为，因为现在匹配的最长后缀长度 <k，所以和原本的 s_i 没有任何关系，因此 s_u+T_j 的最长后缀就等价于 T_j 的最长后缀），所以我们可以类似的把 u 出发的看作是从 w 出发的，同样需要对答案做一个修正，可以发现这里的贡献只和 u 的深度有关，因此可以开个桶存一下每个深度的 u 的贡献，最后可以线性得到答案。

可以在每个节点是维护一个次数 c_i 代表有多少个结点被等效于从 i 出发，然后按照深度从大到小扫每个结点，这样结点会不断被合并上去，一直到最后所有节点都被合并到根。

这里是线性的。

还有一些实现细节：

• 建立 AC 自动机，可以发现 AC 自动机不能暴力跳 fail，而找 fail 实际上就是 fail 链上第一个有某个字符出边的点，可以用可持久化线段树维护每个结点是否有某个字符的出边，这部分是 1\log。
• 对每个 u 找出第一次跳 fail 的点，可以用二分哈希。

时间复杂度 O((n+m)\log n)。