字符串

发表于 更新于 分类于 Waline：
摘要：串串可爱

后缀自动机（SAM）

概述

SAM 是一种很优秀的字符串数据结构。它可以将一个字符串的所有子串压缩成一个 $O(n)$ 大小的结构。

定义

SAM 是有限状态自动机，换种说法就是：

  • SAM 是一个有向无环图。节点被称为状态。边有边权，权值为一个字母，边称为转移。
  • 存在一个源点 $t_0$，即初始状态。从 $t_0$ 出发可以到达所有状态。
  • 存在若干个终止状态。从 $t_0$ 到某个终止状态的路径，边权拼起来一定是 $s$ 的一个后缀。反之，$s$ 的任意一个后缀对应一条从 $t_0$ 到某个终止状态的路径。

SAM 与子串的关系

从 $t_0$ 出发的任意一条路径，边权拼起来一定是 $s$ 的子串。反之，$s$ 的任意子串对应从 $t_0$ 出发的一条路径。

$t_0$ 到每个点可能有多条路径，也就是说每个状态对应一些子串的集合。

引入其它概念

endpos

假设 $s$ 有非空子串 $t$，则 $\operatorname{endpos}(t)$ 表示 $t$ 在 $s$ 中所有出现的结束位置。例如 $s=\texttt{abcbc}$，则 $\operatorname{endpos}(\texttt{bc})=\{3,5\}$。

某几个子串的 $\operatorname{endpos}$ 可能相同，例如 $s=\texttt{abcbc}$，则 $\operatorname{endpos}(\texttt{c})=\operatorname{endpos}(\texttt{bc})=\{3,5\}$。$\operatorname{endpos}$ 相同的子串会被划分到同一个等价类 中， $s$ 的所有子串会被划分成若干个等价类。

SAM 的每个状态对应一个等价类中的所有子串。也就是说，SAM 的状态数为等价类的数量 $+1$，其中 $+1$ 加上的是 $t_0$，$t_0$ 对应的是空串。

引理 1：$u,w$ 是字符串的两个子串，则：$u$ 是 $w$ 的后缀 $\iff$ $\operatorname{endpos}(w) \subseteq \operatorname{endpos}(u)$。

引理 2：在一个等价类中，短的字符串是长的字符串的后缀，且这些字符串长度连续。

现有状态 $u$，假设 $u$ 所对应的等价类中，长度最长的是 $t$。将 $t$ 的所有后缀按长度递减排序，则这个等价类中包含前几个后缀。设第一个不属于这个等价类的后缀为 $w$（一定存在，因为 $w$ 可以为空），则 $\operatorname{link}(u)$ 连向 $w$ 所属的等价类所对应的状态。

所有的后缀链接构成一棵根节点为 $t_0$ 的树。

注意后缀链接 link 的边与 SAM 的边并不相同。

由引理 1 可知，$\operatorname{endpos}(u)\subsetneq\operatorname{endpos}(\operatorname{link}(u))$。

其它定义

对于状态 $u$，其等价类中最长的字符串为 $\operatorname{longest}(u)$，其长度为 $\operatorname{len}(u)$。最短的字符串为 $\operatorname{shortest}(u)$，其长度为 $\operatorname{minlen}(u)$。

可以得出：$\operatorname{minlen}(u)=\operatorname{len}(\operatorname{link}(u))+1$。

SAM 的构建

我们采用在线构建方法，即向 SAM 中逐个加入字符。

先放代码（代码中 $t_0$ 节点的编号为 $1$）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct SAM
{
    int ch[26], len, link;
    // ch[x]: 从这个节点出发的，边权为 x 的边
    // len: 这个点对应的等价类中最长字符串的长度
    // link: 这个点的后缀链接
} t[N];
int tot = 1, lst = 1;
// tot 为 SAM 中点的总数
// lst 为 上一次操作过后整个串对应的节点
void add(int x)
{
    int p = lst, cur = ++tot;
    t[cur].len = t[p].len + 1;
    while (p && !t[p].ch[x]) t[p].ch[x] = cur, p = t[p].link;
    if (!p) t[cur].link = 1;
    else
    {
        int q = t[p].ch[x];
        if (t[p].len + 1 == t[q].len) t[cur].link = q;
        else
        {
            int nw = ++tot;
            t[nw] = t[q];
            t[nw].len = t[p].len + 1;
            t[q].link = t[cur].link = nw;
            while (p && t[p].ch[x] == q) t[p].ch[x] = nw, p = t[p].link;
        }
    }
    lst = tot;
}

我们假设已知字符串 $s$ 的 SAM，现在我们要添加字符 $x$，新的字符串为 $s+x$。

接下来我们看看 $\operatorname{add}$ 函数里代码的作用：

1
2
int p = lst, cur = ++tot;
t[cur].len = t[p].len + 1;

$lst$ 指原串 $s$ 所属的节点，我们记录这个点为 $p$。

同时我们要新建一个节点，记这个节点为 $cur$。

新建节点也就意味着新建了一个等价类，显然这个等价类中最长的字符串为 $s+x$。所以可以求出 $\operatorname{len}(cur)=\operatorname{len}(p)+1$，即 $s$ 的长度 $+1$。

1
while (p && !t[p].ch[x]) t[p].ch[x] = cur, p = t[p].link;

在这个循环中，$p$ 会不停跳到 $\operatorname{link}(p)$，因此 $p$ 对应的字符串永远是原串 $s$ 的后缀。

循环的执行条件 !t[p].ch[x]，意为 $p$ 没有权值为 $x$ 的转移，也就是说 $p$ 中的字符串接上 $x$ 后都没有在原串中出现过。那么此时 $p$ 中所有的字符串接上 $x$ 后仍为同一个等价类，直接把状态 $p$ 添加一个权值为 $x$ 的转移，指向新的等价类 $cur$ 即可。

1
if (!p) t[cur].link = 1;

如果遍历完原串 $s$ 的所有后缀，它们接上 $x$ 都没有在原串中出现过，那么 $s$ 的所有后缀接上 $x$ 都在同一个等价类中，它们的 $\operatorname{endpos}$ 都只有为 $|s|+1$ 这一个元素。直接将这个等价类的 $\operatorname{link}$ 指向 $t_0$ 即可。 

1
2
3
else
{
    int q = t[p].ch[x];

否则，我们在 $p$ 向上跳的过程中，找到了一个等价类，其中的字符串接上 $x$ 在原串中出现过。记 $q$ 为 $p$ 沿着权值为 $x$ 的转移走到的节点。

1
if (t[p].len + 1 == t[q].len) t[cur].link = q;

在这里我们做了一个判断：$\operatorname{len}(p)+1=\operatorname{len}(q)$。如果这个条件满足，说明等价类 $q$ 中只含有一个字符串，这个字符串即为 $\operatorname{longest}(p)+x$。此时将新建的等价类的 $\operatorname{link}$ 指向 $q$ 即可。

否则，$\operatorname{len}(p)+1\neq\operatorname{len}(q)$。我们知道，$\operatorname{shortest}(q)=\operatorname{longest}(p)+x$。所以 $\operatorname{shortest}(q)$ 的 $\operatorname{endpos}$ 在原串的基础上增加了 $|s|+1$ 这一个值，而 $q$ 中其它字符串的 $\operatorname{endpos}$ 均未发生改变。

也就是说字符串加入 $x$ 后，$q$ 中的字符串的 $\operatorname{endpos}$ 不相同了。为了使每个节点的 $\operatorname{endpos}$ 相同，我们需要把 $q$ 拆分成两个等价类，一个只包含 $\operatorname{shortest}(q)$，另一个包含 $q$ 中的其他字符串。

1
2
3
4
int nw = ++tot;
t[nw] = t[q];
t[nw].len = t[p].len + 1;
t[q].link = t[cur].link = nw;

我们新建一个编号为 $nw$ 的节点，它只包含 $\operatorname{shortest}(q)$。它的出边和 $\operatorname{link}$ 应与原先 $q$ 的相同，所以先让 t[nw] = t[q]。现在的 $q$ 应包含除 $\operatorname{shortest}(q)$ 以外的字符串。

然后计算 $\operatorname{len}(nw)$，显然它等于 $\operatorname{len}(p)+1$。

最后，$q$ 和 $cur$ 的 $\operatorname{link}$ 都应连向 $nw$。

1
while (p && t[p].ch[x] == q) t[p].ch[x] = nw, p = t[p].link;

最后，$p$ 的某些后缀的权值为 $x$ 的转移可能指向 $q$，我们应该将他指向 $nw$。

至此，SAM 的就构建完了。