前言
只要你愿意啃，没有算法是学不来的
——教练
说实话，学完 SA 后有时间都会去看 SAM ，但就是怀着信息去，带着一脑子问号回来
根据教练の哲理，一定要把 SAM 啃下来
引入
后缀自动机能解决很多问题。
举个例子
- 在一个字符串中搜索另一个字符串所有出现位置
- 得到有多少本质不同的字串
当然，这些 SA 也能轻易完成
但是 SAM 能做到很多 SA 做不到的 它最大的优势是在线的
而且它有十分优秀的时间复杂度 \(O(n)\)
SAM 的定义
- SAM 是一张有向无环图 只有一个原点 \(t_0\) 称为初始状态 其它所有点都可以通过 \(t_0\) 到达
- 每条边都是一个转移 每个节点都是一个状态
- 每个状态的转移都是不同的
- 存在多个终止状态，满足从原点 \(t_0\) 出发，到达终止状态立得到的字符串的必是原字符串的后缀 并且满足任何 \(S\) 的后缀都可以由一条路径表示
- 满足上述所有条件前提下，SAM 满足节点数最少
SAM 的基本性质
SAM 保证：
- 字符串中的任意一个字串都可以由一条路径表示
- SAM 任意一个节点表示的字符串都是原串 \(S\) 的字串
一些例子
可以前往 OI-wiki 查看
一些重要的概念
endpos
定义：我们记 \(\text{endpos(p)}\) 表示字符串 \(p\) 在原串 \(s\) 中所有出现结束位置的集合。
举个栗子，对于 \(\text{s=ababa}\) 则 \(\text{endpos(ab)}=(2,4)\) ，\(\text{endpos(a)}=(1,3,5)\)
对于两个字串 \(a\) , \(b\) ,若满足 \(\text{endpos(a)}=\text{endpos(b)}\) 我们认为 \(a,b\) 是一个等价类。
因此，\(S\) 里面所有的字串可以分成若干个等价类。
而我们 SAM 中的节点，就是所有等价类带边的点
一些定理/引理
- \(1.1\) 若字符串 \(a,b\) 满足 $\text{endpos(a)}\subseteq\text{endpos(b)}\Leftrightarrow $ \(b\) 为 \(a\) 的后缀
这个感性证明是最好的，自行理解就行
- \(1.2\) 每个等价类包含的字符串长度一定都是在区间 \([x,y]\) 之间的
也是推荐感性理解，长度 \(x\) 以下的是当前集合的超集，\(y\) 以上的是当前集合的子集
这个区间内一定都是连续的数字，因为字串是连续的
不理解可以看看例子
- \(1.3\)
对于任意两个子串 \(a,b\space |a|\le |b|\)
如果 \(a\) 为 \(b\) 的后缀，那么它们满足 \(1.1\)
否则满足 \(endpos(a)\cup endpos(b)=\varnothing\)
根据 \(1.1\) 可以推证
后缀链接 link
先看张图
\(S=abcbc\)
红色的边就是后缀链接
其实用最直白的话来讲 后缀链接就是当前等价类最短后缀的下一个后缀 就是当前等价类的超集
比如说 \(\text{abcbc}\) 它的最短后缀是 \(\text{abc}\) 那么它连接到的就是 \(\text{bc}\) 因为 \(\text{endpos(bc)}=\{2,4\}\)
还是很好理解的 手画一下其它节点都满足这个性质
- \(2.1\) 所有 \(\text{link}\) 构成一棵节点为 \(t_0\) 的树
考虑对于任意节点往后缀链接移动，能满足当前等价类的长度不断变短，最终总能到达 \(t_0\)
根据 \(1.3\) 可以证明不存在环
所有点联通不存在环的无向图就是树
对于这棵树 我们称为 \(\text{parent tree}\)
-
\(2.2\) 对于任意状态，记它的长度区间为 \([l,r]\) 那么对于任意节点 \(x\) 满足 \(l_x\) = \(r_{fa_x}+1\)
-
\(2.3\) 对于任意状态 \(v_0\) 向着 \(\text{link}\) 遍历到 \(t_0\) 经过所有状态长度区间的交集为 \(\{0\to r[v_0]\}\)
即从任意状态往 \(t_0\) 走，可以完成遍历完它的所有后缀
我们 SAM 的状态点与 parent tree 的状态是完全相同的
对于一整个字符串 \(s\) 它只会在 parent tree 中分裂 \(|s|\) 次 所以可以保证节点在最坏条件下是 \(2n-1\) 的
知道这些后，我们可以开始构造 SAM 了