SAM 笔记

SAM 笔记

有人问我 \(\text{endpos}\) 是什么？一个串的 \(\text{endpos}\) 就是它在原串中的所有出现位置右端点集合。

后缀自动机每个节点对应的是一些本质不同的字符串，这些串满足属于同一个等价类，即 \(\text{endpos}\) 相同. 这些串有后缀关系. 后缀链接连向这些串的一个最小后缀（可能为空），使得其 \(\text{endpos}\) 真包含该点的 \(\text{endpos}\).

记录的信息：\(\text{len, link, next[26]}\)；全局有一个 \(\text{sz, last, cur}\)；

初始化 \(\text{len[0] = 0, link[0] = -1, sz = 0, last = 0}\).（写到代码里只需要 link[0] = -1）

\(\text{expand}\)：假设加入字符 \(\text c\)，加入前的字符串为 \(\text s\)

1. \(\text{cur}\gets\) ++\(\text{sz}\)，\(\text{len(cur)} \gets \text{len(last) + 1}\)
2. 从 \(\text{last}\) 遍历后缀链接，若当前 \(\text p\) 无 \(\text c\) 边，就加一条到 \(\text{cur}\).
3. 若遍历到 0，\(\text{link(cur)}\gets 0\)，转 8.
4. 否则找到了一个 \(\text p\) 有 \(\text c\) 出边，停止遍历, 记 \(\text{q = p.next[c]}\)
5. 若 \(\text{len(p) + 1 = len(q)}\)，\(\text{link(cur)} \gets \text{q}\)，转 8.
6. 否则新建 \(\text{copy}\)，\(\text{copy}\) 的 \(\text{link}\)、\(\text{next}\) 复制 \(\text q\) 的，\(\text{len(copy)} \gets \text{len(p) + 1}\)，\(\text{link(q)} \gets \text{copy}\), \(\text{link(cur)} \gets \text{copy}\).
7. 遍历 \(\text p\) 开始的后缀链接，若 \(\text p\) 有 \(\text c\) 边 \(\text p\to\text q\)，则重定向到 \(\text{copy}\)，直到没有 \(\text c\) 边或连向的非 \(\text q\)，转 8.
8. \(\text{last} \gets \text{cur}\). (转 1)

解析（极速版）：（记 \(\text{short(q)}\) 为 \(\text q\) 最短的串，\(\text{long(q)}\) 为 \(\text q\) 最长的串）我们新建了一个等价类 \(\text{cur}\)，前三步可以理解.

第 4 步是找到了当前一个后缀在前面的一个出现 \(\text q\). 这样，这个后缀的 \(\text{endpos}\) 真包含了 \(\text{cur}\) 的 \(\text{endpos}\)（我们找到了一个可以 \(\text{link}\) 的串）. 这样，我们想要 \(\text{cur}\) \(\text{link}\) 向 \(\text q\)，只需要一个条件：这个后缀是 \(\text q\) 中最长的串. 于是，若 \(\text{len(p) + 1 = len(q)}\)，它就显然满足了，可以直接连。

否则它不满足、不能直接连，那我们需要构造一个新等价类，使得它的最长串是这个后缀。然后的大概思路是构造一个 \(\text{copy}\)，把 \(\text q\) 分成新 \(\text q\) 和 \(\text{copy}\) 两份，那现在考虑分裂 \(\text q\) 的影响.

画画图容易看出，\(\text{link(q)}\) 应连向 \(\text{copy}\)，而 \(\text{link(copy)}\) 应该继承之前的 \(\text{link(q)}\)，而显然 \(\text{len(copy) = len(p) + 1}\)，\(\text{link(cur)}\) 指向 \(\text{copy}\)，而原来 \(\text q\) 能下一位走哪些字符，\(\text{copy}\) 当然也可以，故复制之前 \(\text q\) 的所有出边. 这样就有了第 6 步.

什么？你不会画图？那我找个链接吧：/i/l/?n=20&i=blog/1924188/202110/1924188-20211018091040410-273570033.png

这样 \(\text{copy}\) 我们就安排完了，除此之外，我们还要重定向一些出边. 那么从 \(\text p\) 继续遍历后缀链接，由于是从 \(\text p\) 开始遍历后缀，所以若有 \(\text c\) 出边那一定连向 \(\text{copy}\)，剩下的一定还是连向 \(\text q\). 而若出边 \(\text c\) 指向的不是 \(\text q\)（或没有出边 \(\text c\)）了，那说明遍历到比 \(\text{short(q)}\) 还短的后缀了，该后缀不应指向 \(\text{copy}\)，就说明应重定向的边已全定完。退出即可.

第 8 步没什么好讲的.

懂穿了吧 !!!

其他一些性质：

• 点数 \(2n-1 (\texttt{abbb..b})\)，边数 \(3n-4 (\texttt{abbb..bc})\)，时 \(O(n)\)，空 \(O(n|\Sigma|)\)（map：\(O(n\log|\Sigma|)\)）
• 后缀链接树：祖先是它的后缀；\(S_{1..p}\)，\(S_{1..q}\) 的最长公共后缀就是 \(\text{LCA}(\text{v}_{\text{p}},\text{v}_{\text q})\) 对应的串，其中 \(\text{v}_{\text{p}}\) 为位置 \(\text p\) 对应的终点节点；这棵树就是反串的压缩后缀树；每个状态 \(i\) 对应的子串数量为 \(\text{len}(i)-\text{len}(\text{link}(i))\)（显然，但 0 除外），...

分配结束标记：从 \(\text{last}\) 开始跳，标记这些点.

每次加入新字符产生的新子串数目（本质不同）：\(\text{len(cur)-len(link(cur))}\).

完结撒花~~

有人问我为什么不加 LaTeX，因为我懒。

UPD：已添加 LaTeX.