Suffix automaton 后缀自动机小记
本文意图从 sam 的性质解释 sam 的构建原理，使得之后复习时对 sam 的特点有更清晰的理解．
注：文章受 Alew_Wei 的博文 常见字符串算法 II：自动机相关 启发．会有许多相关的应用，感谢．
记号/约定：
- \(T\)：sam 的起点，代表空串的等价类．
- \(t_p\)：从 \(T\) 转移截止到状态 \(p\) 的一个子串．
- \(c_{p, q}\)：状态 \(p\) 转移到状态 \(q\) 的字符．
- \(\delta(p, c)\)：状态 \(p\) 经过 \(c\) 转移到的状态．
- \(endpos(t)\)：字符串 \(t\) 结束位置的集合．
- \(substr(p)\)：状态 \(p\) 代表的子串集合．
- \(shortest(p)\)：状态 \(p\) 代表的最短子串．
- \(longest(p)\)：状态 \(p\) 代表的最长子串．
- \(minlen(p)\)：\(|shortest(p)|\)．
- \(len(p)\)：\(|longest(p)|\)．
- \(link(p)\)：状态 \(p\) 的后缀链接．
一．引理
4 个引理是重要而容易理解的．
- 两子串的 \(endpos\) 包含或不交．
- 对于一个状态 \(p\)，\(substr(p)\) 中的子串连续，并且较短的串是较长的串的后缀．
- 后缀链接构成一棵根节点为 \(T\) 的树．
- 后缀链接构成的树和由 \(endpos\) 包含关系构成的树相同．
对于后缀链接的理解：状态 \(p\) 的后缀链接为 \(q\)，即从 \(longest(p)\) 开始不断丢弃子串前端的字符，直到 \(shortest(p)\) 为止，子串 \(endpos\) 没有改变．继续丢弃前端的字符，子串的 \(endpos\) 会新增加一些位置，变成另一个状态，即 \(q\)．
二．性质/结论
有 sam 的结构结合引理可以得到这些性质．这些性质是很重要的．
- 关于后缀链接
- 从状态 \(p\) 沿后缀链接到 \(T\)，所有状态 \(q\) 的区间 \([minlen(q), len(q)]\) 不交，其并构成区间 \([0, len(p)]\)．
- 从状态 \(p\) 沿后缀链接到 \(T\)，所有状态 \(q\) 的 \(substr(q)\) 的并集构成 \(longest(p)\) 的所有后缀．
- 关于转移
- 若存在转移 \(p \rightarrow q\)，\(\forall t_p\in substr(p), t_p+c_{p, q}\in substr(q)\)．
- \(\forall t_q \in substr(q), \exists t_p(p\rightarrow q),t_p+c_{p,q}=t_q\)．
- 还是转移
- 对于状态 \(q\)，不存在 \(p \rightarrow q,len(p)+1 > len(q)\)．
- 对于状态 \(q\)，唯一存在 \(p \rightarrow q,len(p)+1=len(q)\)．
- 对于状态 \(q\)，唯一存在 \(p \rightarrow q,minlen(p)+1=minlen(q)\)．
到这里，我们回头考察一下这些性质．1 中的性质可以通过 引理 中 对于后缀链接的理解 证明．2 中的性质可以用 sam 的 \(DAWG\) 的性质证明．3 中的性质则是 1 和 2 的结合和补充．
记 \(mxtrs(q)=p\ (p \rightarrow q,len(p)+1=len(q)),\ mntrs(q)=p\ (p \rightarrow q,minlen(p)+1=minlen(q))\)．
- 对于状态 \(q\)，所有 \(p\ (p \rightarrow q)\) 在 parent tree 上形成一段从 \(mxtrs(q)\) 到 \(mntrs(q)\) 深度由深到浅的链．
结论 4 结合前面的结论是容易理解的．
从图上，我们可以这样去理解它：
三．构建
有了 一、二 两部分的铺垫，构造的过程就比较易懂了．考虑新增一个字符 \(c\) 构成的串为 \(s\)，之前的串为 \(s'\)．\(s'+c=s\)．令 \(|s|=n\)．
相较于 \(s'\)，\(s\) 中只多出了一个新子串 \(s\)，只有 \(s\) 的后缀 \(endpos\) 新增了 \(n\)．
在 parent tree 上，我们记一个状态 \(p\) 到 \(T\) 的简单路径经过的状态集合为 \(Rd_p\)．
新建节点 \(np\)，\(endpos(np)=n\)．
\(s\) 的真后缀可以表达为 \(s'\) 的后缀 \(+c\)．设状态 \(p_{s'}\) 满足 \(s' \in p_{s'}\)，$向上遍历 \(Rd_{p_{s'}}\)，在这个过程中处理 \(p \rightarrow np\) 的新增转移并找到 \(link(np)\)．
对于过程中第一个 \(p\in Rd_{p_{s'}}, \exists\delta(p, c)\)，每个之前的节点 \(p'\) 有新增转移 \(\delta (p, c)=np\)．
在这部分中，\(\forall t_{p'}\)，\(t_{p'}+c\) 不属于 \(s'\) 中的任意一种等价类．故 \(t_{p'}+c \in np\)．
记 \(\delta(p, c)=q\)．接下来我们分两种情况讨论：
- \(len(q)=len(p)+1\)．这说明 \(\forall t_q\)，\(t_q\) 为 \(s\) 的后缀．可以直接让 \(link(np)=q\)．
- \(len(q)>len(q)+1\)．这说明 \(\exists t_q\)，\(t_q\) 不是 \(s\) 的后缀．我们把 \(q\) 分为两部分 \(nq,mq\) 分别表示是 \(s\) 后缀的部分和不是 \(s\) 后缀的部分并用两者代替 \(q\)．令 \(link(nq)=link(q),link(mq)=nq,\ len(nq)=len(p)+1,len(mq)=len(q)\)．它们的转移都和 \(q\) 的转移相同．继续跳 \(p\) parent tree 上的祖先 \(p'\)，\(\delta(p', c)\) 能够表达的子串一定 全部 为 \(s\) 的后缀，故不用继续向上检查．直接令 \(link(np)=nq\)．
这之后，我们顺着 \(p\) 向上跳后缀链接，将满足 \(\delta(p', c)=q\) 的点进行操作 \(\delta(p', c) \leftarrow nq\)．
发现我们在上述讨论中完美地构造了状态 \(np\)．构造它的过程中巧妙地串联起来 \(s'\) 和 \(s\) 后缀的关系．
关于增量法构造 sam 的上述讨论，都是和之前所提到的结论相照应的．
在理解时，尤其注意结合 性质 4：对于状态 \(q\)，所有 \(p\ (p \rightarrow q)\) 在 parent tree 上形成一段从 \(mxtrs(q)\) 到 \(mntrs(q)\) 深度由深到浅的链．
四．应用、例题
这部分可能会在以后更新．