2.2.2 SAM

そんな明日が来たなら

如果有那么一天的话

焼き尽くして彗星よ

彗星啊，烧尽一切吧

\[ \rm{Define\ \LaTeX \ Macros\ Here} \newcommand\stirA[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}} \newcommand\stirB[2]{\begin{Bmatrix}#1\\ #2\end{Bmatrix}} \newcommand\ul[1]{\underline{#1}} \newcommand\dis{\operatorname{dis}} \newcommand\edp{\operatorname{edp}} \]

并不推荐阅读本文，本文质量非常差，本文仅作备忘，请阅读 CMD 的文章。

抄写自后缀自动机(干货篇) - Command_Block。

其实我觉得应该先学后缀树再学这玩意。

SAM 是一个可以接受字符串 \(s\) 所有子串的最小自动机。

Endpos 集合¶

我们称 \(s\) 的某个子串的 \(\text{Endpos}\) 集合，是 \(s\) 为后缀的前缀终点的集合，或者说 \(s\) 在原串中的终止位置的集合，记作 \(\edp(s)\)。

例如，在 \(\texttt{abbaab}\) 中，则 \(\edp(\texttt{ab})\) 是 \(\{2,6\}\)，而 \(\edp(\texttt{a})\) 是 \(\{1,4,5\}\)。

我们称所有 \(\text{Endpos}\) 集合相同的子串组成的集合为一个 \(\text{Endpos}\) 等价类。

性质¶

对于两个子串 \(s_1,s_2\)，若 \(s_1\) 是 \(s_2\) 的一个后缀，那么 \(\edp(s_2)\subseteq \edp(s_1)\)。

Proof: 考虑所有 \(s_2\) 出现的位置，\(s_1\) 都一定会出现，注意反之则不然。
若两个子串 \(s_1,s_2\) 有 \(\edp(s_1)\cap \edp(s_2)\neq \varnothing\)，那么必然有一个是另一个的后缀。

Proof: 因为两者 \(\text{Endpos}\) 集合有交，所以必然有某个地方两者同时出现，则一者为另一者的后缀。
在一个 \(\text{Endpos}\) 等价类中，所有的串必为最长串的后缀，且设最短串长度为 \(l\)，最长串的长度为 \(r\)，则等价类大小为 \(r-l+1\)，且对于每个 \(k\in [l,r]\)，均恰有一个子串长度为 \(k\)。

Proof: 由 \(2\) 显然可以得到所有串都是最长串的后缀，设长度最短的子串为 \(t_l\)，最大的为 \(t_r\)，对于每个 \(k\in [l,r]\)，设 \(t_r\) 长度为 \(k\) 的后缀是 \(t_k\)，显然有 \(t_k\) 为 \(t_r\) 的后缀，\(t_l\) 为 \(t_r\) 的后缀，故：

\[ \edp(t_r)\subseteq \edp(t_k)\subseteq \edp(t_l) \]

又 \(\edp(t_l)=\edp(t_r)\)，故 \(\edp(t_k)=\edp(t_r)\)。

Suffix Link Tree¶

显然 \(\text{Endpos}\) 等价类这种要么包含要么相离的结构可以用树来刻画。我们把这棵树叫后缀链接树。

每个 \(\text{Endpos}\) 等价类的父亲，是其 \(\text{Endpos}\) 集合的最小超集。此树上的节点含义与 SAM 节点含义相同，因为对所有 \(\text{Endpos}\) 等价类取并，恰好是原串的所有子串，且任意两个 \(\text{Endpos}\) 等价类不交。

性质¶

后缀链接树节点数为 \(\mathcal O(n)\)。
设 \(u\) 为 \(v\) 在后缀链接树上的父亲，而 \(\operatorname{minlen}(u)\)，\(\operatorname{maxlen}(u)\) 分别表示 \(u\) 这个 \(\text{Endpos}\) 等价类的最短/最长子串的长度，则 \(\operatorname{minlen}(v)=\operatorname{maxlen}(u)+1\)。

构造¶

SAM 的构造是增量构造的，实现是下列代码：

void Extend(const int &c) {
    int cur = newnode(), p = last;
    nd[cur].len = nd[p].len + 1;
    nd[cur].id = ++clen;
    last = cur;

    while (p != -1 && !nd[p][c])
        nd[p][c] = cur, p = nd[p].Link;
    if (p == -1) {
        nd[cur].Link = 0;
        return ;
    }

    int q = nd[p][c];
    if (nd[q].len == nd[p].len + 1) {
        nd[cur].Link = q;
    } else {
        int clone = newnode();
        nd[clone] = nd[q];
        nd[clone].id = 0;
        // 更新 len, 更新 Link, 更新转移
        nd[clone].len = nd[p].len + 1;
        nd[q].Link = nd[cur].Link = clone;
        while (p != -1 && nd[p][c] == q)
            nd[p][c] = clone, p = nd[p].Link;
    }
}

上面的函数维护了加入一个字符 \(c\) 后 SAM 的变化，其中 last 是上一次原串被包含的节点。nd[u][c] 是节点 \(u\) 的转移 \(c\)。

nd[cur].len = nd[p].len + 1;
nd[cur].id = ++clen;
last = cur;

while (p != -1 && !nd[p][c])
    nd[p][c] = cur, p = nd[p].Link;

nd[cur].id 指的是这个 \(\text{Endpos}\) 等价类第一次出现的位置。其他就是维护一下长度。

现在 \(u\) 这个 \(\text{Endpos}\) 等价类里只有当前串一个元素。

第二段的 while 是说，不断跳 \(\text{Endpos}\) 等价类的极小超集，对于每个祖先的 \(\text{Endpos}\) 等价类里的串（当前加入的是第 \(i\) 个字符，显然这些都是 \([1,i-1]\) 的一段不断缩短的后缀），在加入一个 \(c\) 之后都会转移到当前这个状态。

------??###c---###c
|        ->       |

即这里的第一个 | 向后移动的过程，直到某个 \(\text{Endpos}\) 等价类里存在了与当前相同的转移。也就是我们要不断将 | 向后移动，直到找到第一个不止在 \([1,i]\) 的后缀中出现的 \([1,i]\) 的后缀。它所在的 \(\text{Endpos}\) 集合当然就是 \(cur\) 的极小超集。

if (p == -1) {
    nd[cur].Link = 0;
    return ;
}

这里就是说对于 \([1,i-1]\) 的任何一个后缀加上 \(c\)，都没有在原来的串里出现过，那也就不存在这一组 \(\text{Endpos}\) 集合的超集（这些串唯一的出现就是在 \([1,i]\) 的后缀），所以它的父亲是空，即根节点 \(0\)。

int q = nd[p][c];
if (nd[q].len == nd[p].len + 1) {
    nd[cur].Link = q;
} else {
    int clone = newnode();
    nd[clone] = nd[q];
    nd[clone].id = 0;
    // 更新 len, 更新 Link, 更新转移
    nd[clone].len = nd[p].len + 1;
    nd[q].Link = nd[cur].Link = clone;
    while (p != -1 && nd[p][c] == q)
        nd[p][c] = clone, p = nd[p].Link;
}

考虑上述的例子

------??###c---###c
               | |

nd[p].len 就是 ### 的长度，设 \(q\) 的代表元是前面的 ??###c。如果 \(q\) 这个 \(\text{Endpos}\) 代表元只有 ###c 这一段（?? 为空串），那么任何一个这个等价类的子串都会在后面再次出现，不需要分裂。

反之，如果 nd[p].len + 1 != nd[q].len，即 ?? 不是空串，那么 ?###c，??###c 等都不会在后面再次出现，它们只出现在前面，而 ###c 的子串还出现在了后面，它们现在应当分属两个不同的 \(\text{Endpos}\) 集合。

我们令原来的 \(\text{Endpos}\) 等价类表示形如 ??###c 的子串，显然它不需要修改。再新建一个节点，表示形如 ###c 的子串，把原来节点的转移复制过来，由于现在 ###c 是 ??###c 的一段后缀，所以 ??###c 的父亲应该设为 ###c，它的 \(\text{Endpos}\) 集合才是 ??###c \(\text{Endpos}\) 集合的最小超集（仅多加了一个 \(i\)）。

然后我们还需要把一些转移边改成指向新建的节点，即 ### 所在 \(\text{Endpos}\) 等价类，及其祖先的指向 \(q\) 的转移 \(c\)。

通过这种方式构建出来的自动机，至多有 \(2|s|-1\) 个节点，\(3|s|-4\) 条转移。

SAM 的应用¶

性质¶

正串 SAM 的后缀链接树是反串的后缀树。
SAM 每条路径都唯一对应一个子串，所以 SAM 的转移 DAG 上至多有 \(\mathcal O(n^2)\) 条不同的，从 \(\varnothing\) 出发的路径。
由 \(2\)，\(t\) 是 \(s\) 的子串，当且仅当从 \(s\) 的 SAM 上 \(\varnothing\) 开始，第 \(i\) 步走转移 \(t_i\)，不会走出这个 SAM。
也可以把 SAM 看成把 \(s\) 所有子串插入 ACAM，然后压缩得到的结构。