后缀自动机（SAM）学习笔记

目录

• 定义
  • 状态集
    • 一些性质
  • 后缀链接
  • 转移函数
    • 性质
• 算法实现
  • 构造方法

写在前面：这篇博客是最近在 (SAM) 的学习过程中记录下的笔记，大部分内容都来自 zjp 以及 hihocoder 两篇博客写的都已经很完善了，但我依然写下的这篇博客，目的也算是展示我的理解以及督促学习。

定义

我们依然引入以上博客的概念。
对于字符串 (S=aabbabd) ，它的后缀自动机是：

对于 (S) 的所有子串，我们都可以通过（蓝色实线 ）转移，最终到达一个合法状态（图中的结点），而其他不是 (S) 子串的字符串，最终会“无路可走”。对于上面的 绿色虚线 便是通常所指的后缀链接，这也是 (SAM) 的利器。

状态集

首先我们引入概念 (endpos) ：子串的结束位置的集合。
对于一个子串 (s) ，(endpos(s)) 是 (s) 在 (S) 中所有出现的结束位置的集合。
以(S="aabbabd")为例

状态	子串	endpos
S	空串	{0,1,2,3,4,5,6}
1	(a)	{1,2,5}
2	(aa)	{2}
3	(aab)	{3}
4	(aabb,abb,bb)	{4}
5	(b)	{3,4,6}
6	(aabba,abba,bba,ba)	{5}
7	(aabbab,abbab,bbab,bab)	{6}
8	(ab)	{3,6}
9	(aabbabd,abbabd,bbabd,babd,abd,bd,d)	{7}

这些状态就是上面 (SAM) 图中的状态。

一些性质

其实观察上表我们也能发现这些性质：

1. 首先对于 (S) 的两个子串(s_1) 和 (s_2) ，不妨设(|s_1| leq |s_2|)，那么 (s_1) 是 (s_2) 的后缀当且仅当 (endpos(s_1) ⊇ endpos(s_2)) ，(s_1)不是 (s_2) 的后缀当且仅当 (endpos(s_1) ∩ endpos(s_2) = ∅) 。

证明不在赘述，有兴趣的可以看上面两篇博客。

2. 一个状态包含的子串都具有相同的 (endpos)，它们都互为后缀。

我们把所有的子串按 (endpos) 分类，每一类就代表了一种状态，所以我们认为一个状态包含了若干个子串。

3. 我们用 (substrings(st)) 表示状态 (st) 中包含的所有子串的集合，(longest(st)) 表示 (st) 包含的最长的子串，(shortest(st)) 表示 (st) 包含的最短的子串。
   那么显然对于一个状态 (st) ，以及任意 (s∈substrings(st))，都有 (s) 是(longest(st)) 的后缀。
   且对于一个状态 (st)，以及任意的 (longest(st)) 的后缀 (s) ，如果 (s) 的长度满足：(|shortest(st)| leq |s| leq |longsest(st)|)，那么 (s∈substrings(st)) 。

后缀链接

这么说，(substrings(st)) 包含的其实是 (longest(st)) 的一系列连续后缀？

比如状态 (7)，包含的子串依次是(aabbab,abbab,bbab,bab)。按照连续的规律下一个子串应该是 (ab)，但是 (ab) 没在状态 (7) 里。

但同时我们又发现了，(substrings(st)) 没有包含 (longest(st)) 的所有后缀。

(aabbab,abbab,bbab,bab)的(endpos)都是({ 6 })，下一个 (ab) 当然也在结束位置 (6) 出现过，但是(ab) 还在结束位置 (3) 出现过，所以 (ab) 比(aabbab,abbab,bbab,bab) 出现次数更多，于是就被分配到一个新的状态中了。

也就是说当 (longest(st)) 的某个后缀 (s) 在新的位置出现时，这一系列连续的后缀就会“断掉”，(s) 会属于新的状态。
我们继续看 (SAM) 图中的状态，又会发现，当某个后缀断掉时，我们通过绿色虚线 将这些状态连了起来形成了一条路径（或者说一个序列），按照状态 (7) 的例子，我们发现这样一条状态序列，(7 o 8 o5 o S)。它的意义在于 (aabbab) 的后缀依次在状态(7，8，5，S)中，并通过后缀链接 (link) 连接起来。
我们由此也知道了 (link) 的作用。

转移函数

我们定义这样一个函数：(next（st）=｛S[i+1] |i ∈ endpos(st)｝)。(next(S)={S[1], S[2], S[3], S[4], S[5], S[6], S[7]}={a, b, d}，next(8)={S[4], S[7]}={b, d}。)

性质

对于一个状态 (st) 和(forall c in next(st))，
(substrings(st)) 中的所有子串后面接上一个字符 (c) 之后，新的子串仍然都属于同一个状态。

比如对于状态 (4) ，(next(4)={a})，(aabb,abbb,bb) 后面接上字符 (a) 得到 (aabba),(abba),(bba) ，这些子串都属于状态 (6) 。

所以我们可以定义转移函数 ：(trans(st, c) ={ x | longest(st) + c ∈ substrings(x)})。也就是说，我们在 (longest(st)) 后面接上一个字符 (c) 得到一个新的子串 (s)，找到包含 (s)的状态 (x) ，那么 (trans(st, c)) 就等于(x) 。

算法实现

构造方法

(SAM)具有(O(|S|))的构造方法，但相对的，对于每个状态不能保存太多数据。对于状态 (st) 我们只保存如下数据，并通过这些数据构造 (SAM)：

数据	含义
(maxlen[st])	(st) 包含的最长子串的长度
(minlen[st])	(st) 包含的最短子串的长度
(trans[st][1..c])	(st) 的转移函数, (c) 为字符集大小
(link[st])	(st) 的后缀链接

然后我们依次添加每个字符，假设已经构造好了 (S[1..i]) 的 (SAM) 。现在要添加(S[i+1])，于是我们新增了 (i+1) 个 (S[i+1]) 的后缀要识别：(S[1..i+1], S[2..i+1], ... S[i..i+1], S[i+1]) 。
考虑到这些新增状态分别是从 (S[1..i], S[2..i], S[3..i], ... , S[i], \_)(空串)通过字符 (S[i+1]) 转移过来的，所以我们还要对 (S[1..i], S[2..i], S[3..i], ... , S[i], \_)(空串) 对应的状态们增加相应的转移。
我们假设 (S[1..i]) 对应的状态是 (u) ，等价于 (S[1..i]∈ substrings(u)) 。根据上面的叙述我们知道 (S[1..i], S[2..i], S[3..i], ... , S[i], \_)(空串) 对应的状态们恰好就是从 (u) 到初始状态 (S) 的由 (Link) ( 绿色虚线 )连接起来路径上的所有状态，不妨称这条路径(上所有状态集合)是(suffix-path(u o S))。
显然至少(S[1..i+1])这个子串不能被以前的 (SAM) 识别，所以我们至少需要添加一个状态 (z) ，(z) 至少包含 (S[1..i+1]) 这个子串。
下面来讲最关键的点，也就是如何添加转移：

1. 首先考虑一种最简单的情况：对于(suffix-path(u o S))的任意状态 (v) ，都有 (trans[v][S[i+1]]=NULL) 。这时我们只要令 (trans[v][S[i+1]]=z) ，并且令 (link[st]=S) 即可。

   例如我们已经得到 (aa) 的 (SAM) ，现在希望构造 (aab) 的 (SAM) 。如下图所示：
   
   此时 (u=2)，(z=3) ，(suffix-path(u o S))是桔色状态组成的路径(2 o1 o S)。并且这 (3) 个状态都没有对应字符 (b) 的转移。所以我们只要添加红色转移(trans[2][b]=trans[1][b]=trans[S][b]=z) 即可。同时令(link[3]=S)。

2. 那要是 (suffix-path(u->S))上有一个节点 (v) ，使得 (trans[v][S[i+1]]!=NULL) 又该怎么办？
   我们以下图为例，假设我们已经构造 (aabb) 的 (SAM) 如图，现在我们要增加一个字符 (a) 构造 (aabba) 的 (SAM) 。

   
   这时 (u=4，z=6，suffix-path(u->S)) 是桔色状态组成的路径(4 o5 o S)。对于状态 (4) 和状态 (5) ，由于它们都没有对应字符 (a) 的转移，所以我们只要添加红色转移 (trans[4][a]=trans[5][a]=z=6) 即可。但是面对 (S) 时，(trans[S][a]=1) 已经存在，这时应该怎么办？

   我们可以认为在 (suffix-path(u o S)) 遇到的第一个状态 (v) 满足 (trans[v][S[i+1]]=x) 。这时我们需要讨论 (x) 包含的子串的情况：

   1. 如果 (x) 中包含的最长子串就是 (v) 中包含的最长子串接上字符 (S[i+1]) ，等价于 (maxlen(v)+1=maxlen(x)) ，比如在上面的例子里，(v=S, x=1，longest(v))是空串，(longest(1)=a) 就是 (longest(v)+a) 。这种情况比较简单，我们只要增加 (link[z]=x) 即可。
   2. 如果 (x) 中包含的最长子串 不是 (v) 中包含的最长子串接上字符 (S[i+1]) ，等价于(maxlen(v)+1 < maxlen(x)) 。这也是最麻烦的情况，我们用下图表示这种情况，这时增加的字符是(c) ，状态是 (z)。

   
   在 (suffix-path(u o S)) 这条路径上，从 (u) 开始有一部分连续的状态满足 (trans[u..][c]=NULL) ，对于这部分状态我们只需增加 (trans[u..][c]=z) 。紧接着有一部分连续的状态 (v..w) 满足 (trans[v..w][c]=x)，并且 (longest(v)+c) 不等于 (longest(x)) 。

   这时我们需要从(x)拆分出新的状态(y)，并且把原来(x)中长度小于等于(longest(v)+c)的子串分给(y)，其余字串留给(x)。同时令(trans[v..w][c]=y)，(link[y]=slink[x], link[x]=link[z]=y)。
   举个栗子:

   假设我们已经构造 (aab) 的 (SAM) 如图，现在我们要增加一个字符 (b) 构造 (aabb) 的 (SAM) 。
   
   当我们处理在 (suffix-path(u o S)) 上的状态 (S) 时，遇到 (trans[S][b]=3) 。并且 (longest(3)=aab) ，(longest(S)+b=b) ，两者不相等。
   其实不相等意味增加了新字符后 (endpos(aab)) 已经不等于 (endpos(b)) ，势必这两个子串不能同属一个状态 (3) 。这时我们就要从 (3) 中新拆分出一个状态 (5) ，把 (b) 及其后缀分给 (5) ，其余的子串留给 (3) 。同时令 (trans[S][b]=5, link[5]=link[3]=S, link[3]=link[4]=5。)

这也与我们的期望一致，至此整个算法结束。
我们不难看出由于是从 (link) 处断开，所以(minlen[i]=maxlen[link[i]]+1;)
因此我们可以再最后求 (minlen)。
代码如下：

int maxlen[N<<1],trans[N<<1][26],link[N<<1],tot=1,last=1;
inline void extend(int id)
{
    int cur=++tot,p;
    maxlen[cur]=maxlen[last]+1;
    for(p=last;p&&!trans[p][id];p=link[p]) trans[p][id]=cur;
    if(!p) link[cur]=1;
    else
    {
        int x=trans[p][id];
        if(maxlen[x]==maxlen[p]+1) link[cur]=x;
        else
        {
            int y=++tot;
            maxlen[y]=maxlen[p]+1;
            for(int i=0;i<26;i++) trans[y][i]=trans[x][i];
            link[y]=link[x];
            for(;p&&trans[p][id]==x;p=link[p]) trans[p][id]=y;
            link[cur]=link[x]=y;
        }
    }
    last=cur;
}

其实看起来挺简单的，相对于(SA)数组来说意外的简洁。