DAG链剖分

_ANIG_ · 2025-07-02 21:12:51 · 算法·理论

本文介绍的是针对于 SAM 上的 DAG 链剖分。

前置知识：SAM，树链剖分。

众所周知，我们可以快速在 SAM 上找到一个字符串，并且可以用一个节点在 parent 树上到根节点的路径表示一个字符串的所有后缀，但是无法很方便地表示一个字符串的所有前缀。

考虑一个字符串的所有前缀在 SAM 上对应的点是什么。

由于在一个字符串末尾添加字符相当于在 SAM 的 DAG 上走一条边，所以一个字符串的所有前缀对应了 DAG 上的一条路径。

考虑用类似树链剖分的思想，将 DAG 剖分成若干条重链，使得任意一条路径都可以拆分为 O(\log n) 段重链。

设 f_x 表示在 DAG 上以 x 结尾的路径条数，g_x 表示以 x 开头的路径条数。

设 F_x 表示 x 连向的点中 g 最大的那个，G_x 表示连向 x 的点中 f 最大的那个，如果有最大值相同则任意取。

如果对于一条边 x,y，满足 F_x=y 且 G_y=x，则将这条边设置为重边，其余边设置为轻边。

则任意一条路径都能被剖分为 O(\log n) 条重链。

证明：

首先，g_x=1+\sum\limits_{(x,y)\in E}g_y。

若 x 连向的点 u 满足 u\neq F_x，则 g_u\le g_{F_x},g_u<g_x-g_{F_x}，所以 g_u\le \frac {g_x}2。

同理，若连向 x 的 u 满足 u\neq G_x，则 f_u\le \frac{f_x}2。

设 p_x 表示 x 这个前缀在 DAG 上对应的点，显然 f_{p_x} 单调递增，g_{p_x} 单调递减。

如果边 p_x,p_{x+1} 是轻边，则要么 f 至少乘 2，要么 g 至少除以 2，又因为 SAM 的 DAG 上总路径条数是关于 n 的多项式级别的，所以一条路径上不会有超过 O(\log n) 条轻边。

具体实现可以直接通过二分哈希，实现 O(\log^2n) 单次剖分。使用后缀数组求 lcp 可以做到 O(\log n) 剖分。

有了这个做法后，我们可以做很多东西。

• 基本子串字典

求区间最短 border、最长 border、border 个数。

考虑一个前缀是 border 的条件，也就是若 S_{[l,i]} 是 S_{[l,r]} 的后缀，则 S_{[l,i]} 是 S_{[l,r]} 的 border。