SAM 所要干的事情,就是对母串 S 构建一个自动机,满足

  • 能接受,且仅能接受母串 S 的子串(下简称子串)
  • 在所有这样的自动机中,SAM 的状态数、边数最少

SAM 的结构

SAM 实际上由两部分组成:用于运行输入字符串的 DAWG(Directed Acyclic Word Graph, DAWG)和用于构建 DAWG 的辅助结构 Parent 树。

但是两个结构的节点是共同的,具体而言,SAM 上的一个节点(或者说状态),对应的是母串中所有 \text{endpos} 相同的子串。

\text{endpos}(T) 指的是串 T 在母串 S 中所有出现的结束的位置。我们发现可以根据 \text{endpos} 划分为若干个等价类,每个等价类就是 SAM 上的一个节点。

\text{endpos} 是很优美的,他有许多很好的性质。

  • 一个 \text{endpos} 等价类中的节点,必定有一个最长的串 T,然后剩下的所有串,都是 T 的后缀,然后这些串的长度都是连续的。我们记一个等价类 u 中的最长串为 \max(u),最短串为 \min(u),那么等价类中一定有且仅有每一个长度度在 [|\min(u)|, |\max(u)|]\max(u) 的后缀。因此,一个长度、一个等价类,就可以唯一确定一个串。

  • 两个串的 \text{endpos} 要么相同,要么有包含关系,要么不交。因此,若干个“包含关系”,可以通过若干条连接相邻两个“层”的边(这两个“层”必定存在后缀的关系),来组成一棵树。实际上这棵树就是 Parent 树。即,一个等价类在 Parent 树上的父亲 \text{link}(u) 是在所有不同于自己的,包含自己的 \text{endpos} 的等价类中,|\max(u)| 最大的那个。我们发现 |\max(\text{link}(u))| + 1 = |\min(u)| 这个事实,以及只要一步一步爬 \text{link},就可以遍历所有 u 的后缀。

我们记从 DAWG 的转移函数为 \delta(u, c),表示从节点 u 末尾添加字符 c 所到达的节点。

SAM 的构造

有一个 O(n) 的,增量的构造方法,每一次我们在母串末尾添加一个字符,并维护添加之后的母串的 DAWG 和 Parent Tree(简称 PT)。

先维护 DAWG

假设我们已经得到了没有添加末尾字符 c 的母串的 DAWG 和 PT,并且在 DAWG 上运行没有添加末尾字符 c 的母串,走到的节点为 v_0,那么接下来我们尝试加入字符 c 并维护 DAWG 和 PT。

首先我们需要新建一个节点,因为在加入之前,DAWG 不可能接受加入之后的整个字符串,所以必定需要新建一个节点 u 表示 \text{endpos} 为最后一个位置的所有子串。并且显然 \delta(v_0, c) = u

那么我们想要找到所有需要执行 \delta(x, c) \leftarrow u 的点,并加上这条边。

这些点,必然是 v_0 的后缀。这是很显然的,因此我们就想通过遍历所有 v_0 的后缀来加边,即跳 v_0\text{link},对于每一个在 \text{link} 链(我们称 PT 上根到 v_0 的这条链为“\text{link} 链”。)上的节点,我们都需要执行 \delta(x, c) \leftarrow u 的操作。

但是,如果存在一个 \text{link} 链上的 v_i,满足 \delta(v_i, c) 已经有出边了,那么这个时候我们不能执行赋值的操作。并且对于从 v_i 向上跳 \text{link}(v_i) 到达的点 v_j,显然 \delta(v_j, c) 也已经有出边了,所以我们不再加入边。

再来看 link

还有 \text{link}(u) 没有维护,如果不存在这样的 v_i,那么我们就把初始节点设为 \text{link}(u)。这代表着 u 是新加入的一个字符。

但如果存在这样的 v_i 呢?我们记 \delta(v_i, c) = v,并再次声明,我们需要找到 \text{link}(u):在所有不同于自己的,包含自己的 \text{endpos} 的等价类中,|\max(v)| 最大的那个。

那么 v 是怎样的一个节点呢?

  • \text{endpos} 等价类 v 中,必定存在一个串 T,满足这个串是整个母串的后缀。这是因为我们通过找到加入末尾字符之前的母串的后缀,再在末尾加入一个末尾字符,而找到的 v
  • \text{endpos}(v) \neq \text{endpos}(u),这是显然的,因为 v\text{endpos} 不止有最后一位。
  • |\max(v)| 必定最大。因为如果存在其他的这样的等价类,那么必定在 \text{link} 链上会更早出现一个有 \delta(v_i, c) 的转移的 v_i

所以,v 就是我们要找的 \text{link}(u)

但是注意到,不是所有结束于 v 的路径,都经过了 v_i\rightarrow v 这条边。如果存在从其他不在 \text{link} 链上的点到 v 的路径,那么在 v 中就存在一些,不是 u 的后缀的字符串。为了保证 \text{link}(u) 一定指向自己的后缀这个性质,我们需要把 v 给拆开。

  • 别忙,我们需要思考一下如何方便地判断是否存在从其他不在 \text{link} 链上的点到 v 的路径。

    对于那些从 \text{link} 链上出发,到 v 形成的字符串,其长度必定小于等于 |\max(v_i)| + 1。这是因为这些点都是 v 的真后缀,然后 v_i 是这些串中最长的那个。

    对于那些从 \text{link} 链外的点 t 出发,到 v 形成的字符串,其长度必定大于 |\max(v_i)| + 1。实际上 v_i\text{endpos} 必定包含 t\text{endpos}。因为如果 v_i 不是 t 的后缀,那么不可能从 v_it 出发都能走到 v。因此 v 中如果含有长度大于 |\max(v_i)| + 1 的字符串,那么就说明存在这样的 t

    因此我们只需要判断 |\max(v)||\max(v_i)| + 1 的大小关系即可。

  • 那么,如果判断出需要拆点,又该怎么拆?

    通过刚刚的分析,我们已经知道,v 如果要拆,那么一定是拆成长度小于 |\max(u)| 的串和大于等于的串——小于的一定来自 \text{link} 链,即是 u 的后缀;大于等于的一定是 v_i 的后代。因此我们拆出来一个新点 v' 代表小于等于的串。我们需要把所有走到 v 的点,且长度小于 |\max(u)|(就是 \text{link} 链上的点)全部更新为,走到 v'。以 v' 继承 v\text{link}。并将 v\text{link} 设为 v'。最后还需要让 v'\delta 等于 v\delta。最后的最后,是 \text{link}(u) \leftarrow v'

实现

struct SuffixAutoMaton {
    #define trans(u, c) (t[u].son[c])
    const int S0 = 0;
    int lst, node_cnt = 0, curlen;
    struct Node { int len, link; unordered_map<int, int> son; } t[MAXN << 1];
    SuffixAutoMaton() { t[node_cnt].link = -1; }
    void extend(int c) {
        int u = ++node_cnt;
        t[u].len = ++curlen;
        while (~lst && !t[lst].son.count(c)) trans(lst, c) = u, lst = t[lst].link;
        if (lst == -1) { t[u].link = S0, lst = u; return ; }
        int v = trans(lst, c);
        if (t[lst].len + 1 == t[v].len) { t[u].link = v, lst = u; return ; }
        int clone = ++node_cnt; t[clone].len = t[lst].len + 1, t[clone].son = t[v].son, t[clone].link = t[v].link, t[v].link = t[u].link = clone;
        while (~lst && trans(lst, c) == v) trans(lst, c) = clone, lst = t[lst].link;
        lst = u;
    }
} SAM;

复杂度

啊嘞嘞,为啥是 O(n) 的啊?小编也不知道,总之 SAM 的复杂度就是 O(n) 的,小编也感到疑惑 =3=

总而言之,SAM 的状态个数上界是 2n - 1(这个挺好证明的,考虑 \text{endpos} 构成树形结构解可),转移个数不超过 3n - 3(这个实在不会证明),我们的复杂度主要来源是加边和加点(将走到 v 的转移更改到走到 v',也因为一些有趣的原因(这个实在不会证明),总的复杂度是 O(n) 的),所以均摊下来就是 O(n) 的了。

OI-字符串 OI-字符串-SAM后缀自动机

fhq-Treap 速查笔记
上一篇 «
字符串学习笔记总览
» 下一篇