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

字符串 学习笔记

注：文中所有字符串位置从1开始
注：若无特别标出，文中所有子串均为可空子串
注：空串在文中用下划线_表示
注：初始状态与空串代表的状态意义相同
注：文中状态，结点与$endpos$等价类是同一概念。
注：图中实线表示DAWG边，虚线表示后缀link。

引入

SP1811 LCS - Longest Common Substring
题意：求两个字符串的最长公共子串长度。
数据范围：$1\leqslant |s|\leqslant 250000$。

• 我会暴力！
• • $O(n)$枚举子串长度
• • $O(n^2)$枚举在两个字符串中的起始位置
• • $O(n)$字符串比较
• • 总复杂度$O(n^4)$
• 我会暴力优化！
• • $O(n^2)$枚举在两个字符串中的起始位置
• • $O(n)$不断增加子串长度，计算哈希值，同时进行字符串比较
• • 总复杂度$O(n^3)$
• 我会二分+哈希！
• • 过程略
• • 总复杂度$O(n\log^2 n)$

前两个算法不可以通过本题，二分哈希虽然能通过，但数据加强就也无能为力了。

我们需要一个更优秀的算法——最好有线性复杂度，它就是后缀自动机，又称SAM（Suffix AutoMaton）。

SAM的定义

SAM是一个能接受字符串所有后缀的最小DFA（确定性有限自动机），同时它其实也可以表示这个字符串的所有子串。

即可以理解为：SAM是一张DAG（其实这个定义不是特别准确，后面会讲），从SAM的起点开始走，可以通过一些边（相当于字符）进行转移，只有字符串的后缀才能到终止集合（注意，终点不止一个，但起点只有一个），且SAM的结点数是最少的。

学SAM需要知道的

结束位置集合$endpos$

我们定义$endpos(t)$为子串$t$在$s$出现的所有结束位置的集合。（注意，我们定义空串的$endpos$为所有位置组成的集合）

举个例子，对于字符串$s=aabaabb$，$endpos(a)=\{1,2,4,5\}$，$endpos(ab)=\{3,6\}$，$endpos(aab)=\{3,6\}$。

$endpos$等价类

我们定义$endpos$等价类为所有$endpos$相同的子串构成的集合。

还是上面这个例子：对于字符串$s=aabaabb$，$endpos$等价类$\{3,6\}=\{ab,aab\}$。

后缀link

对于一个$endpos$等价类，它在从长到短排序后一定满足后面的字符串是前面的字符串的子串（这个在后面会进行证明），因此我们定义后缀link为两个$endpos$等价类之间的有向边，且$u$能向$v$连后缀link当且仅当$u\subseteq v$且$v$是具有这个性质的$v$中集合大小最小的。

这里再举个例子吧，对于字符串$ababab$，它的所有$endpos$等价类为：$\{1,2,3,4,5,6\}$对应$\{\_\}$，$\{1,3,5\}$对应$\{a\}$，$\{2,4,6\}$对应$\{b,ab\}$，$\{3,5\}$对应$\{ba,aba\}$，$\{4,6\}$对应$\{bab,abab\}$，$\{5\}$对应$\{baba,ababa\}$，$\{6\}$对应$\{babab,ababab\}$，因此它对应的后缀$link$会连成这样的形式：

$\{1,3,5\}\rightarrow\{1,2,3,4,5,6\}$
$\{2,4,6\}\rightarrow\{1,2,3,4,5,6\}$
$\{3,5\}\rightarrow\{1,3,5\}$
$\{4,6\}\rightarrow\{2,4,6\}$
$\{5\}\rightarrow\{3,5\}$
$\{6\}\rightarrow\{4,6\}$

终止集合&终止链

对于每一个后缀形成的$endpos$等价类，形成的是终止集合，它们的后缀link一定会形成一条链，我们称这条链为终止链。

Parent Tree

根据后缀link将所有$endpos$等价类连成的结构叫做Parent Tree。因为所有非空子串代表的集合都会连向大小严格大于它的集合，而空串代表的集合又是最大的，因此这是一颗以空串代表的集合为根结点的树，这棵树有一些优秀的性质，我们之后再讲。

比如，根据字符串$ababab$，我们构建出来的Parent Tree为：

DAWG（Directed Acyclic Word Graph）

定义DAWG为能表示字符串所有后缀的图，其中每一个结点都是一个$endpos$等价类，可以完成SAM的基本操作。

形成DAWG的DAWG边带权，表示某个$endpos$等价类在后面添加一个字符可以转移到另一个$endpos$等价类。

DAWG的构造会在后面讲到，这里用上面的字符串$ababab$举个例子吧：

其实DAWG和Parent Tree是共用一套结点的，只是边不一样而已。

连续的转移

设$len_x$为$x$代表的$endpos$等价类最长串的长度，那么如果一条从$u$连向$v$的DAWG边满足$len_u+1=len_v$，我们就称这条DAWG的转移是连续的，否则就称是不连续的。

SAM的性质

性质1：对于两个非空子串$a,b$（$|a|\leqslant|b|$），$a\in suffix(b)\Leftrightarrow endpos(b)\subseteq endpos(a)$，$a\notin suffix(b)\Leftrightarrow endpos(a)\cap endpos(b)=\varnothing$

首先证第一个：因为$a$是$b$的后缀，所以$b$结束的所有地方$a$一定结束，即$endpos(b)\subseteq endpos(a)$。反之，如果$endpos(b)\subseteq endpop(a)$，那么$b$结束的地方$a$一定结束，又因为$|a|\leqslant|b|$，因此$a$是$b$的后缀。

第一个成立，则证明了$a\in suffix(b)$与$endpos(b)\subseteq endpos(a)$互为充要条件，反之也可以知道$a\notin suffix(b)\Leftrightarrow endpos(b)\nsubseteq endpos(a)$。又因为$|a|\leqslant |b|$，所以$endpos(a)\nsubseteq endpos(b)$，因此$a\notin suffix(b)\Leftrightarrow endpos(a)\cap endpos(b)=\varnothing$。

性质2：将一个$endpos$等价类的所有字符串按长度从大到小排序后，每一个字符串都是其前面的字符串的后缀，且这些后缀是连续的（即长度严格递增）

考虑$endpos$等价类中两个字符串$a$与$b$（$|a|\leqslant|b|$），$endpos(a)=endpos(b)$，由引理1得$b$为$a$的后缀。

然后我们设$endpos$等价类中最长的子串为$ls$，最短的子串为$ss$，$s$为$ls$的一个后缀且$|ls|\geqslant|s|\geqslant|ss|$，那么肯定有$s\in suffix(ls),ss\in suffix(s)$，由引理1得$endpos(ls)\subseteq endpos(s)\subseteq endpos(ss)$，又因为$ls,ss$属于一个$endpos$等价类，所以$endpos(ls)=endpos(ss)$，故$endpos(ls)=endpos(s)=endpos(ss)$，即$s$属于这个$endpos$等价类。

因此，我们证明了一个$endpos$等价类中最长的子串的所有长度大于等于这个等价类中最短子串的后缀都属于这个$endpos$等价类，即里面的后缀是连续的。

性质3：$endpos$等价类的级别为$O(n)$

考虑一颗表示长度为$n$的字符串的Parent Tree，由引理1和后缀link的定义可以知道任意父结点的所有儿子一定都是这个父结点互不相交的子集，且每个子节点的大小必定小于父亲结点的大小，因此可以考虑分割关系，根结点的子集大小为$n$，最多进行$n-1$次分割，即产生$n-1$对父子关系，因此$endpos$等价类的级别是$O(n)$。

这个不懂没关系，在证明复杂度的时候会再次提及（以另一种方式）。

性质4：若存在$u$连向$v$的后缀link，那么$minlen(u)=maxlen(v)+1$

上面讲过，后缀link可以看做分割关系，即被连向的状态分割成所有连向它的状态（注意，某些$endpos$可能会丢失，这个后面会讲到），因此，我们可以考虑在某一个Parent Tree中非叶子节点代表的$endpos$等价类中最长串前面添加一个字母，使得它的$endpos$不属于这个结点的$endpos$等价类，因此这是一个新的$endpos$等价类，而根据后缀link的定义，它的后缀link应该连向原来的结点。某些结点可能是串的前缀，在前面是无法添加字母的，因此可能会丢失一些$endpos$。

有了这个性质，我们可以在构造SAM的时候少保存一些信息。

性质5：从初始状态到任意状态，有且仅有一条完全由连续转移组成的路径到达

这个很显然，因为跳连续转移意味着在后面添加字符，如果有两条完全由连续转移组成的路径，那么这两条路径一定是重合的。

SAM的构造

SAM一般指Parent Tree与DAWG一整套结构，下面我们对这两个结构的构造进行讲解：

DAWG

DAWG可以用一种叫做增量法的方式进行在线构造：

首先定义变量：$len_i$指$endpos$等价类$i$中最长的子串，$link_i$指$i$的后缀link，$nxt_{i,c}$指$i$可以通过字符$c$转移到什么状态。

由于是在线构造，因此我们考虑每次都加入字符$c$，当前位置为$p$（当前位置为当前后缀自动机表示的串所处的$endpos$等价类），并让新字符串中所有的后缀被表示出来。

我们考虑哪些点需要更新，由于要让所有的后缀被表示出来，因此只需要之前的最长后缀代表的$endpos$等价类$last$到空串代表的$endpos$等价类（即新的终止链）都可以转移到表示现在所有后缀的状态就可以了。

那么我们首先新建一个结点$now$，代表这些新后缀代表的$endpos$等价类，很显然$len_{now}=len_{last}+1$（即新的串为旧的串后面添加一个字符），我们只需要将所有上述状态用一条字符为$c$的边连向$now$就可以完成构建了。

看一种情况：

我们需要将终止链上的状态连向$now$，然后考虑$now$的后缀link怎么连，因为是$now$这个状态代表的$endpos$为$\{p\}$，而没有其他的状态代表的$endpos$中含有位置$p$，所以$now$的后缀link需要连向$root$（即空串表示的状态）。

但是远远没有这么简单，在下图中，$v3$已经有一条字符为$c$的边了，此时该怎么处理呢？

首先还是新建状态$now$，并连接$v1$和$v2$连向$now$的边。

此时，我们需要分类讨论一下：

如果$len_{v3}+1=len_d$，即$v3$最长的子串后面添一个字符$c$就是状态$d$的最长子串，那么$d$一定代表的最长串为$t+c$，其中$t$为$v3$中最长的串，也是$v1$中最长的串$s$的子串。而$now$代表的最长串为$s+c$，$t+c$是$s+c$的后缀，故$now$需要向$d$连后缀link。（不过此时$x$结点不存在，可以思考一下）

否则，$len_{v3}+1<len_d$（因为不可能大于，如果大于那么肯定存在更优的属于$d$状态的串$t+c$使$len_d=len_{v3}+1$），这就有一个严重的问题：$d$中所有的子串，有些在$v3$更新后会多一个地方结束，导致$d$不属于一个$endpos$等价类、

此时我们需要克隆出一个新状态$r$存储$v3$更新后会影响的子串，因为这些子串可以通过原先$d$的DAWG边进行转移，所以我们要先让它接受所有$d$的$nxt$信息（即连出的DAWG边）。

考虑如何更新各个经过修改的结点的后缀link：$now$的后缀link，$d$的后缀link，$r$的后缀link。

因为存在$v1$到$v3$的后缀link组成的路径，所以$d$最长串$t+c$（$t$为$v3$中某一个串）为$now$最长串$s+c$（$s$为$v1$最长串）的后缀，所以$now$的后缀link可以连向$r$。

同理，因为$r$为$v3$某些串加上字符$c$构成的$endpos$等价类，所以$r$最长串可以用$t'+c$表示（$t'$为$v3$中某一个串）。考虑$t$和$t'$的关系，因为加上字符$c$后$t$结束的地方不会改变而$t'$出现的地方会改变，所以肯定$t'$长度小于$t$，又因为$t$和$t'$属于一个$endpos$等价类，所以$t'+c$是$t+c$的后缀，$t+c$的$endpos$一定是$t'+c$的$endpos$的子集，即$d$的后缀link需要连向$r$。

同时，由于$d$原本的后缀link连向$y$，由引理4可以知道$y$中所有的串都是$d$中所有的串的后缀，在克隆之后$r$会替代$d$将后缀link连向$y$。

最后，我们遍历剩余的终止链，由于$v3$后加$c$可以转移到状态$d$，所以$v4$以及之后的状态加$c$都可以转移到状态$d$，因此这些状态都会有一条字符为$c$的DAWG边连向状态$d$，更新之后可以通过这些状态加$c$转移到的子串的$endpos$一定会改变，因此它们的字符$c$边需要连向$r$。

当然，这条终止链上可能还有其他的结点，它们如果不指向状态$d$，那么一定会有一条同样字符的边指向其他的状态（$d$以前的后缀link一定会连向这些状态），这时候我们就不用管了。

代码（原则：理解性默写）：

int extend(int last,int x){
    int now=++tot,pos=last,tmp,cln;
    len[now]=len[last]+1;
    while(pos!=0&&nxt[pos][x]==0)
        nxt[pos][x]=now,pos=link[pos];
    if(pos==0){
        link[now]=1;
        return now;
    }
    tmp=nxt[pos][x];
    if(len[tmp]==len[pos]+1){
        link[now]=tmp;
        return now;
    }
    cln=++tot;
    for(int i=1;i<=26;i++)
        nxt[cln][i]=nxt[tmp][i];
    len[cln]=len[pos]+1;
    link[cln]=link[tmp],link[tmp]=link[now]=cln;
    while(pos!=0&&nxt[pos][x]==tmp)
        nxt[pos][x]=cln,pos=link[pos];
    return now;
}

主函数内，维护一下$last$就可以了：

cin>>s;
n=s.size(),s=" "+s;
last=++tot;
for(i=1;i<=n;i++)
    last=extend(last,s[i]-96);

Parent Tree

Parent Tree很容易建，只需要把所有后缀link连边就好了。（注意，为了让空串代表的状态为根结点，因此需要反着建边）

代码：

for(i=2;i<=tot;i++)
    add(link[i],i);

DAWG和Parent Tree的差别与联系

• DAWG的结点和Parent Tree中的的结点相同。
  由定义可得。
• 跳DAWG边意味着在后面添加一个字符，跳后缀link意味着在前面减少若干个字符。
  由DAWG边的定义，第一句话显然。
  由后缀link的定义，我们知道存在后缀link的两条状态的$endpos$等价类是包含关系，即存在后缀关系，那么跳后缀便意味着在前面减少若干个字符。
• 在后面添加一个字符一定会跳DAWG边，而在前面减少若干个字符不一定会跳后缀link。
  由DAWG边的定义，第一句话显然。
  因为每一个结点表示的是一个$endpos$等价类，所以可能代表多个串，因此在前面减少若干个字符不一定会跳后缀link。
• DAWG是一个DAG（Directed Acyclic Graph，有向无环图），而Parent Tree是一棵树。
  因为跳DAWG边长度会增加，所以长度只增不减，一定无法形成环，因此DAWG是一个DAG。
  除空串外，所有状态都会有一条后缀link指向其他的状态，因此Parent Tree是一棵树。

SAM的正确性证明

因为每一次添加字符一定会让当前的终止链中所有结点（包括空串代表的状态）存在一条边权为这个字符的DAWG边，所以SAM一定可以表示出字符串的所有后缀，进一步，也可以表示字符串的所有子串。（因为走后缀的时候一定会走过后缀的前缀，而子串可以理解为后缀的前缀）

SAM的复杂度证明

这里假定字符集大小是常数，那么SAM的复杂度为$O(n)$，否则SAM的复杂度为$O(n|\Sigma|)$（$n$为字符串长度，$|\Sigma|$为字符集大小）

SAM的状态数是$O(n)$的

按照建SAM的过程，有一个初始状态（空串），第一次添加状态和第二次添加状态的时候不可能进行克隆，后面每一次都有可能进行克隆，因此总状态数最多为$1+1+1+2\cdot (n-2)=2n-1$，是$O(n)$的。

实际上，存在状态数达到上限的情况：$abb\cdots bb$。

因为SAM中所有结点是这个串所有的$endpos$等价类，所以自然$endpos$等价类的级别也是$O(n)$的。

SAM的转移数是$O(n)$的

我们构造以空串代表的状态为根的最长路径生成树，那么这个生成树上的转移一定是连续的转移（否则一定找得出一条更长的路径来代替树上不连续的转移）。我们称在最长路径生成树上的转移为树边，其他的转移为非树边。因此有且仅有一条路径可以通过树边从根走到任意结点。

我们考虑每一条非树边$a\rightarrow b$（边权为$c$），我们可以用字符串$u+c+w$来表示从空串代表的状态到$a$状态的最长路径$u$（那么$u$一定在最长路径生成树上），$a\rightarrow b$的边权$c$，状态$b$到终止状态的最长路径$v$。那么，如果非树边的$a$不同，其他的相同，那么在最长路径生成树上的$u$一定不同；如果转移的$b$不同，$a$相同，那么一定$c$不相同（由DAWG边的定义可得）；如果$c$不相同，那么这条路径也一定不相同。因此，我们可以发现每一条非树边都只能映射到一条这样的路径，即非树边和这些路径是单射的。

得到了非树边和路径是单射的后，我们考虑这些路径的含义：因为这些路径都是从空串代表的状态到终止状态的路径，因此每一条路径都代表字符串的一个后缀，且完整串代表的后缀一定不在这些路径上（因为完整串代表的路径上的转移一定都是连续的，而由SAM的性质“初始状态到某一状态连续转移组成的路径一定只有一条”得完整串代表的路径一定在最长路径生成树上），所以非树边的个数为真后缀（即非完整串的后缀）代表的路径的个数，因此非树边最多有$n-1$条。

最长路径生成树的边数（即转移数）为点数减一，点数最多为$2n-1$，因此树边总数最多为$2n-2$。加上$n-1$条非树边，SAM的转移数最多为$3n-3$，为$O(n)$的。

实际上，SAM的转移数无法到达上界，因为如果状态数达到了上界，那么串一定是$abb\cdots bb$的形式，而它的转移数却无法到达$3n-3$（如果状态数无法到达上界，那么转移数也无法到达上界）。所以SAM的转移数真正的上界是$3n-4$，且存在情况使转移数到达上界：$abb\cdots bbc$。

构建SAM的时间复杂度是$O(n)$的

我们看SAM的构建代码：

int extend(int last,int x){
    int now=++tot,pos=last,tmp,cln;
    len[now]=len[last]+1;
    while(pos!=0&&nxt[pos][x]==0)
        nxt[pos][x]=now,pos=link[pos];
    if(pos==0){
        link[now]=1;
        return now;
    }
    tmp=nxt[pos][x];
    if(len[tmp]==len[pos]+1){
        link[now]=tmp;
        return now;
    }
    cln=++tot;
    for(int i=1;i<=26;i++)
        nxt[cln][i]=nxt[tmp][i];
    len[cln]=len[pos]+1;
    link[cln]=link[tmp],link[tmp]=link[now]=cln;
    while(pos!=0&&nxt[pos][x]==tmp)
        nxt[pos][x]=cln,pos=link[pos];
    return now;
}

首先，里面非循环的复杂度是$O(1)$，而$extend$的次数是$n$次，所以非循环的总复杂度是$O(n)$的。

然后，我们看向$3$个循环：

• 第$1$个循环：我们将终止链上所有没有$c$字符转移的状态添加一个转移到$now$（即每循环到一个$pos$都会添加一个转移），由于转移数不会减少，转移数是$O(n)$的，所以这个循环总复杂度一定是$O(n)$的。
• 第$2$个循环：同样的，$cln$一开始没有转移，只有第$2$个循环才会给$cln$新的转移，由于转移数是$O(n)$的，所以这个循环总复杂度也是$O(n)$的。
• 第$3$个循环：这个循环的复杂度不是很明显，因为这里是将一个转移转移到另一个状态。我们从另一个角度来看，我们是把所有$nxt_{pos,x}=tmp$的DAWG边重定向到$cln$，考虑$nxt_{pos,x}=tmp$的边是怎么得来的——第一二个循环！而我们知道第$1,2$个循环的次数是$O(n)$的，所以产生的$nxt_{pos,x}$一定是$O(n)$的，我们重定向的次数也最多是$O(n)$的。（自己瞎想的，不知道对不对）

故，我们证明了一个很美妙的性质——SAM的时间复杂度是$O(n)$的！

SAM的复杂度优化

上面，我们证明了SAM的复杂度是$O(n)$的，但是，如果字符集过大，那么字符集大小$|\Sigma|$也会对复杂度进行影响，我们需要更优的复杂度！

• 对字符集进行离散化（显然），$|\Sigma|$优化为$O(n)$级别。
• 用$map$对$nxt$的存储与复制进行加速：考虑$nxt$只有赋值和复制两个操作，我们可以通过$map$优化$nxt$的赋值操作，使字符集大小变成$\log$级别的，即复杂度优化成$O(n\log|\Sigma|)$

代码很简单（离散化不给出）：

map<int,int>nxt[maxn];
int extend(int last,int x){
    int now=++tot,pos=last,tmp,cln;
    len[now]=len[last]+1;
    while(pos!=0&&nxt[pos][x]==0)
        nxt[pos][x]=now,pos=link[pos];
    if(pos==0){
        link[now]=1;
        return now;
    }
    tmp=nxt[pos][x];
    if(len[tmp]==len[pos]+1){
        link[now]=tmp;
        return now;
    }
    cln=++tot;
    nxt[cln]=nxt[tmp]; 
    len[cln]=len[pos]+1;
    link[cln]=link[tmp],link[tmp]=link[now]=cln;
    while(pos!=0&&nxt[pos][x]==tmp)
        nxt[pos][x]=cln,pos=link[pos];
    return now;
}

SAM的应用

下一篇：后缀自动机（SAM）应用与做题记录

其他

参考文献：

• 后缀自动机 (SAM)
• 史上最通俗的后缀自动机详解
• 后缀自动机（SAM）学习笔记
• 后缀自动机感性理解
• 震惊！SAM复杂度竟如此显然！
• 浅谈后缀自动机
• 后缀自动机多图详解（代码实现）
• A short guide to suffix automata
• 后缀自动机学习笔记(干货篇)

好东西：SAM生成器