火萤Ⅳ型，已就位：后缀自动机（SAM）学习笔记

· · 算法·理论

声明：本文部分内容经过 AI 润色。

博客

你这是哪个 SAM

后缀自动机，简称 SAM，是一种我认为非常复杂的自动机，但是它也有很多优秀的特点，所以能够处理很多问题，很多后缀数组问题也都能用后缀自动机完成。

整体结构

SAM 的内部包含两套边，理解这两套边是掌握 SAM 的关键。

第一套边：带字符的转移边

可以通过类似 Trie 树的方式在这个图上转移，但整个图形成了一张有向无环图，而不是树。

从初始状态出发，沿着转移边走，经过的边上的字符连起来形成的字符串，恰好是原串的某一个子串。并且原串的每个子串都对应这样的一条路径。

注意，多个不同的子串可能走到同一个状态，因此 SAM 可以压缩很多状态。

第二套边：后缀链接（Parent 树）

后缀链接指向的一个状态，其子串是在其它状态中为其后缀且最长的状态。

其中每个状态代表一个 endpos 等价类：即该状态包含的所有子串，它们每次出现时的结束位置集合完全相同。

随着状态不断迁移到后缀链接位置，子串终止位置不变，但是长度变小，我们发现 endpos 必定增多，且一定包含原本的 endpos。

再反过来思考一下，对于一个子串，在它的左边添加一个字符，这个字符决定了这个子串之后可能出现在哪里，对于不同字符，对应的位置是不一样的。

因此我们把每个后缀链接连边，形成一棵树，通常称为 Parent 树 或后缀链接树。

那么一个节点的 endpos 集合是其所有子节点 endpos 集合的并集，并且子节点之间的 endpos 集合互不相交。当然对于初始状态空串设定 endpos 就是所有位置。

对于一个子串，在它的前面加上字符的同时在原字符串中仍然存在的方案可能只有一种，因此 SAM 会对其进行压缩，用 len 表示其最长长度。

那么由之前一次次加入字符的角度考虑，一个状态代表的子串长度是连续且不重复的，并且在长度为 len 之后会产生不同结果（或者无法进行），那么长度的区间为 (len[fa], len]。

根据我们不断缩短后缀的方式，我们可以发现两个状态在 Parent 树上的 LCA 所代表的最长子串，就是这两个状态对应子串的最长公共后缀。

构造方法

只要我们通过整体结构，知道这个 SAM 是需要干什么的，要维护怎样的内容，构造的方法也就比较好想了。

我们按照顺序，一个一个加入字符串的节点到自动机中。

我们加入一个之后，首先考虑保持 Trie 树的结构。

那么我们显然需要把所有在上一个加入的字符之后加上一个新的字符，需要跳转之前的串的所有的后缀。

对于这个后缀没有之后的点为加入的字符的情况，那么直接给它加上新的转移点。

如果加入所有后缀都没有这个字符，那么这个新建节点就是唯一一个可以以这个点为结束位置的，直接把后缀链接连到初始位置。

否则，有一个后缀在前面出现的地方后面有这个字符。

比如：abceeeab 后面加上一个 c 的话。

那么此时 ab 所代表的子串已经有后面存在 c 的情况了，看看怎么处理。

对于不带有 c 这个字符的转移的，直接将这个转移到新建点即可。

等处理到后缀 ab 时，这个点已经有这个转移了，那么我们这个点就没有必要成为之后的其它后缀的转移点了。

所以直接把后缀链接设到这个点的 c 转移的那个状态就行了，因为这是除 c 外这个字符串中最长的且有下一个 c 转移的后缀，因此就是新字符串的最长后缀。

但是这样就正确了吗？

你迫不及待地拿了一个串 abb 想要试试。

你把最后一个 b 放上去，它的后缀链接连接着上一个 b 所在的状态。

最后得到这样一张图：

你发现这样好像确实可以从根走到每一个点，但是你忘了需要满足每个点代表的子串结束位置要相同！

我们发现节点 3 同时表示了 b 和 ab 两个子串。

这种情况下对于上一个 b 所在的状态会出现它同时代表 ab 和 b 两个字符串。

但是 ab 并不是 abb 的后缀，并且两个子串的结束位置完全不同！

这是为什么？

我们在走 Trie 树上的边得到的结果，并不是我们到哪个节点就表示哪个子串，而是根据我们走的路径上有哪些字符！

所以，我们从那个有 b 转移的地方走了一个 b 的话，形成的新子串长度应该只加一，但是由于那个状态还包含了其他更长的子串，它的 len 未必就是多一的。

解决方法也很简单，我们再克隆一个新状态，把它的 len 设为当前这个点的 len 加一即可，它的其它信息（转移边和后缀链接）和原本的这个错误的选择节点一样。

我们把新克隆出来的点作为后缀链接指向的节点就行了。

这个克隆操作的本质其实是将原本 SAM 压缩的一个状态给重新分成了两个状态，这两种状态原本所要维护的东西除了最长长度外完全一致。

因此，注意要修改之前的一些点，让其 Trie 树上的儿子改为这个克隆出来的点，比如其中的节点 1，因为我们相当于把原本的节点 3 给拆了，而对于我们所遍历的后缀在 Trie 树上的结构就是要选择被克隆出来的新节点。

得到的结果如图：

经过复制操作，并且对一部分边进行重定向后，我们就得到了正确的后缀自动机。

这样就完成了整个 SAM 的构造，只要理解了 SAM 的整体结构，还是比较好理解的。

后缀自动机 洛谷 - P3804

::::success[看看代码（可结合注释食用）]

#include<bits/stdc++.h>
using namespace std;
char s[1000005];
int n,siz[2000005];
long long ans;
struct SAM{
    struct P{
        int son[26],len,fa;
    }c[2000005];
    int la=1,id=1;
    void insert(int v){
        int p=la;
        int np=la=++id;//新添加的点
        siz[np]=1;
        c[np].len=c[p].len+1;//p为上次添加的点，这次新的整串长度就是之前长度+1
        while(p&&!c[p].son[v])c[p].son[v]=np,p=c[p].fa;//给所有上一个整串的后缀加上这一字符转移
        if(!p)c[np].fa=1;//全部转完了，这个新节点没有可链接的后缀
        else {
            int q=c[p].son[v];
            if(c[q].len==c[p].len+1)c[np].fa=q;//这就是一个新节点后缀
            else {
                int nq=++id;
                c[nq]=c[q];//克隆新节点
                c[nq].len=c[p].len+1;//最长长度设为len[p]+1，这样就可以作为新节点后缀
                c[q].fa=c[np].fa=nq;
                while(p&&c[p].son[v]==q)c[p].son[v]=nq,p=c[p].fa;//由于p点走一步就是新节点，那么其后缀不可能更长，所以直接把所有到q的转移改成nq
            }
        }
    }
}sa;
vector<int> e[2000005];
void dfs(int p){
    for(int i:e[p]){
        dfs(i);
        siz[p]+=siz[i];
    }
    if(siz[p]>1)ans=max(ans,1ll*siz[p]*sa.c[p].len);
}
signed main(){
    cin>>s+1;
    n=strlen(s+1);
    for(int i=1;i<=n;i++)sa.insert(s[i]-'a');
    for(int i=2;i<=sa.id;i++)e[sa.c[i].fa].push_back(i);
    dfs(1);
    cout<<ans;
    return 0;
}

::::

点数、边数、复杂度分析

点数

SAM 拥有非常优秀的性质，它的总点数最多是字符串长度的两倍。

这是由于每次只会增加一个点，然后可能会克隆一个点，所以就是两倍的点数。

那么容易得到状态数最多为 2n 了。

但是实际上界差不多是 2n-1，除了 n=1 的情况外很难达到上界，只需要写代码的时候开两倍就行了。

边数

至于边数，考虑起来则比较复杂了。

首先考虑所有长度为 len[u] + 1 == len[v] 的情况。

显然对于每一个状态，都只会有一条满足这个性质的边。

除了初始状态外，所有点的 len 都是某个点的 len 加一得到的，也就是每个除了初始状态外都有一条边。

那么结合大部分情况下的点数上界，有 2n-2 条。

然后考虑其它边。

这时候有一个非常厉害的性质，我们要求从初始位置开始，找到必须经过这条转移边的最长路径。

由于每个点都是一个点的 len 加一得到的，因此经过这条边的最长路径肯定全部都是加一的路径了。

由于之后没有其它状态了，所以这一定对应一个这个字符串的后缀。

每个子串都对应一个路径，所以这种边肯定只会有对应后缀的数量，总共有 n-1 条。

那么总的边数大概就是 3n-3 了，实际上很多时候只有 3n-4，总之就是差不多 3n，非常优秀。

时间复杂度

讨论时间复杂度的时候，我们先假定字符集大小很小，可以忽略，视为常数，不然连边的时间复杂度搞不好还要带一只 \log。

发现时间复杂度的瓶颈肯定在两个 while 循环上。

考虑 while 循环会循环几次。

我们每次都是在上一次初始的节点开始的。

跳一次就是直接到达其后缀链接的位置。

我们看看这个后缀链接。

我们发现，其后缀链接要么是初始位置，要么是在上一次遍历到的节点的 len 加一处。

那么每次都加一，但是跳转后缀链接时一定会让长度减小，所以总共的时间复杂度是 O(n) 的！

但是其实你开数组的时候就已经给它乘上了一个字符集大小，所以还是要注意的，可能部分题目需要用 map 来存，不然空间给你爆了。

广义后缀自动机

然而有的时候我们可能需要把多个字符串放入一个 SAM 里面。

实际上处理这种问题的方法有很多，比如直接在中间插入分隔符，但是这样在处理较多字符串时效率较低，部分问题需要特判分隔符的影响，比较麻烦。

对于直接把 last 重新放到初始位置的做法，其时间复杂度无法得到保障。

为了使时间复杂度仍然被保证，我们考虑把相同的字符合在一起进行处理。

显然可以构建一个 Trie 树，这样对于树上的每个节点，其儿子所代表的字符都是互不相同的。

BFS 遍历 Trie 树。当处理 Trie 节点 u 时，我们已经知道了它在 SAM 中对应的状态编号 pos[u]（也就是插入 u 这个字符序列后的 last）。对于 u 的每一个儿子字符 c，我们把 last 设置为 pos[u] 后，再加入字符 c，并把返回的新状态赋值给儿子节点。

这样就把相同字符的干扰去掉了，由于 Trie 上每个节点的子节点字符互不相同，因此在 BFS 建 SAM 时，每次 insert 操作面对的 last 状态都不会发生这个字符已经转移过的情况，由于不同字符插入同一个 last 再操作上互不干扰，保证了总复杂度仍为 O(\sum|S_i|) 的（如果不把字符集大小当成常数，那就再乘上，不过一般用到的时候都不会很大）。

因此我们直接 BFS 下去，把 last 设为每个点的父亲加入后的 last，不断插入即可。

注意这里是 BFS 而不是 DFS，我们发现如果你继续在之后添加，那么之前提到的“由于不同字符插入同一个 last 再操作上互不干扰”这个性质就失效了，所以应该使用 BFS 而非 DFS。

BFS 做法时间复杂度得证，那么对于 DFS 做法是否可以进行优化？那么是否可以优化把 last 重新放到初始位置的做法并得到一种在线构造方法？答案是可行的。

本文仅证明了 BFS 写法正确性，但是未涉及其它做法。感谢 @Wxb2010 提出的不足。在 DFS 和在线做法中，我们可以通过两个特判来规避时间复杂度的问题，整体思路是通过两个特判来解决，笔者最近比较忙，先搁置一下，对于这些做法有兴趣的可以看 【【模板】广义后缀自动机（广义SAM）】- 辰星凌 ，其中有对这些构造方法的详细说明。

::::success[看看代码]

void add(string s){
    int p=0;
    for(int i=0;i<s.size();i++){
        if(!tr[p][s[i]-'a'])tr[p][s[i]-'a']=++id;
        p=tr[p][s[i]-'a'];
    }
}
int la;
struct P{
    int son[26],fail,len;
}c[4000005];
void insert(int x){
    int p=la;
    int np=la=++id;
    c[np].len=c[p].len+1;
    while(~p&&!c[p].son[x])c[p].son[x]=np,p=c[p].fail;
    if(p==-1)c[np].fail=0;
    else {
        int q=c[p].son[x];
        if(c[q].len==c[p].len+1)c[np].fail=q;
        else {
            int nq=++id;
            c[nq]=c[q];
            c[nq].len=c[p].len+1;
            c[np].fail=c[q].fail=nq;
            while(~p&&c[p].son[x]==q)c[p].son[x]=nq,p=c[p].fail;
        }
    }
}
void build(){
    id=0;c[0].fail=-1;
    queue<pair<int,int>> q;
    q.push({0,0});
    while(!q.empty()){
        pair<int,int> u=q.front();
        q.pop();
        for(int i=0;i<26;i++)if(tr[u.first][i]){
            la=u.second;
            insert(i);
            q.push({tr[u.first][i],la});
        }
    }
}

::::

应用

不同子串个数

不同子串个数 洛谷 - P2408

直接建出 SAM，然后由于每个子串都只对应一个节点，并且每个节点的代表的所有字符串长度连续，所以可以直接通过 len 减去 len[fa] 加一作为子串数量。

把每个点加起来即可。

::::success[看看代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
char s[100005];
vector<int> e[200005];
struct SAM{
    struct P{
        int son[26],len,fa;
    }c[200005];
    int la=1,id=1;
    void insert(int x){
        int p=la;
        int np=la=++id;
        c[np].len=c[p].len+1;
        while(p&&!c[p].son[x])c[p].son[x]=np,p=c[p].fa;
        if(!p)c[np].fa=1;
        else {
            int q=c[p].son[x];
            if(c[q].len==c[p].len+1)c[np].fa=q;
            else {
                int nq=++id;
                c[nq]=c[q];
                c[nq].len=c[p].len+1;
                c[q].fa=c[np].fa=nq;
                while(p&&c[p].son[x]==q)c[p].son[x]=nq,p=c[p].fa;
            }
        }
    }
    void dfs(int p){
        for(int i:e[p]){
            ans+=c[i].len-c[p].len;
            dfs(i);
        }
    }
}sam;
signed main(){
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)sam.insert(s[i]-'a');
    for(int i=2;i<=sam.id;i++)e[sam.c[i].fa].push_back(i);
    sam.dfs(1);
    cout<<ans;
    return 0;
}

::::

弦论

弦论 洛谷 - P3975

首先这是一个子串的问题，可以考虑使用 SAM 来处理。

我们先建出 SAM，然后我们考虑如何统计答案：从初始状态开始，得到后面选择一个字符会有多少子串，通过字典序要求得到下一位是什么，以此类推。

那么我们就需要得到每个点之后有多少子串。

由于图是 DAG 并且不同路径带来的结果不同，我们可以直接统计所有到达的，所以只需要得到在每个点结束的答案即可。

对于要求每种不同的算一个的时候，显然一个点结束只能对应一个答案，因此每个都只记录一个即可。

对于需要计算不同的，我们给每个终止位置所有的最长的子串节点加上一个 endpos 大小。

之后可以通过 Parent 树的优秀性质，把一个点的儿子的 endpos 数量加起来就是这个点 endpos 数量。

那么知道了 endpos 的数量，这个节点可以结束的位置也就是这个数量了，可以轻松计算最终结果了。

::::success[看看代码]

#include<bits/stdc++.h>
using namespace std;
char s[500005];
int op,k,siz[1000005],n;
long long f[1000005];
vector<int> e[1000005];
struct SAM{
    struct P{
        int son[26],len,fa;
    }c[1000005];
    int la=1,id=1;
    void insert(int x){
        int p=la;
        int np=la=++id;
        siz[id]=1;
        c[np].len=c[p].len+1;
        while(p&&!c[p].son[x])c[p].son[x]=np,p=c[p].fa;
        if(!p)c[np].fa=1;
        else {
            int q=c[p].son[x];
            if(c[q].len==c[p].len+1)c[np].fa=q;
            else {
                int nq=++id;
                c[nq]=c[q];
                c[nq].len=c[p].len+1;
                c[q].fa=c[np].fa=nq;
                while(p&&c[p].son[x]==q)c[p].son[x]=nq,p=c[p].fa;
            }
        }
    }
    void build(){
        for(int i=1;i<=n;i++)insert(s[i]-'a');
        for(int i=2;i<=id;i++)e[c[i].fa].push_back(i);
    }
    void dfs(int p){
        for(int i:e[p])dfs(i),siz[p]+=siz[i];
        f[p]=siz[p];
    }
    bool vis[1000005];
    void dfs2(int p){
        if(vis[p])return;
        vis[p]=1;
        for(int i=0;i<26;i++)if(c[p].son[i]){
            dfs2(c[p].son[i]);
            f[p]+=f[c[p].son[i]];
        }
    }
    void solve(){
        if(!op)for(int i=1;i<=id;i++)f[i]=siz[i]=1;
        else dfs(1);
        f[1]=siz[1]=0;
        dfs2(1);
    }
    void query(int p,int k){
        if(k<=siz[p])return;
        k-=siz[p];
        for(int i=0;i<26;i++){
            int v=c[p].son[i];
            if(f[v]<k)k-=f[v];
            else {
                putchar('a'+i);
                query(v,k);
                return;
            }
        }
    }
}sam;
signed main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    cin>>op>>k;
    sam.build();
    sam.solve();
    if(f[1]<k)cout<<-1;
    else sam.query(1,k);
    return 0;
}

::::

Longest Common Substring

Longest Common Substring HDU - 1403

对于求两个字符串的最长公共子串问题，可以先对其中一个建立后缀自动机。

然后，另一个字符串仍然考虑枚举结束在哪里。

如果这个节点没有下一个字符的转移，那就不断跳到后缀链接位置，直到无法再跳或者可以转移。

最后答案取一个最大值即可。

::::success[看看代码]

#include<bits/stdc++.h>
using namespace std;
char s[100005],t[100005];
struct SAM{
    struct P{
        int son[26],len,fa;
        void clear(){
            memset(son,0,sizeof(son));
            len=fa=0;
        }
    }c[200005];
    int la=1,id=1;
    void init(){
        la=1,id=1;
        c[1].clear();
    }
    void insert(int x){
        int p=la;
        int np=la=++id;
        c[np].clear();
        c[np].len=c[p].len+1;
        while(p&&!c[p].son[x])c[p].son[x]=np,p=c[p].fa;
        if(!p)c[np].fa=1;
        else {
            int q=c[p].son[x];
            if(c[p].len+1==c[q].len)c[np].fa=q;
            else {
                int nq=++id;
                c[nq].clear();
                c[nq]=c[q];
                c[nq].len=c[p].len+1;
                c[np].fa=c[q].fa=nq;
                while(p&&c[p].son[x]==q)c[p].son[x]=nq,p=c[p].fa;
            }
        }
    }
    int query(){
        int lent=strlen(t+1);
        int p=1,l=0,res=0;
        for(int i=1;i<=lent;i++){
            int x=t[i]-'a';
            while(p>1&&!c[p].son[x])p=c[p].fa,l=c[p].len;
            if(c[p].son[x])l++,p=c[p].son[x];
            res=max(res,l);
        }
        return res;
    }
}sam;
signed main(){
    while(~scanf("%s%s",s+1,t+1)){
        sam.init();
        int len=strlen(s+1);
        for(int i=1;i<=len;i++)sam.insert(s[i]-'a');
        printf("%d\n",sam.query());
    }
    return 0;
}
//hhq

::::

LCS Spanning Tree

LCS Spanning Tree 洛谷 - P9664

这道题还是稍微有点难度的。

多个字符串，可以使用广义后缀自动机。

我们要求最大生成树，考虑经典的贪心方法。

由于代价是最长公共子串的长度，所以考虑使用 SA 或者 SAM 来解决。

SA 是可做的，但是 SAM 专题我要用 SAM。

我们首先建出广义后缀自动机。

考虑把每个字符串的子串分为多组，每组对应一个以某个点为结尾的点。

我们首先把每组子串长度最长的情况下对应到的 SAM 上节点找到。

对于同一个 SAM 节点上的，这个点对应字符串的最长长度就是考虑这个节点时二者的最长公共后缀。

为了贪心，直接把所有点按照长度排序，递减顺序处理。

每次处理完一个点，但是可能还有后缀和它匹配，只是没有那么长。

那么每次处理完一个节点，就向上传一个这个点的原有后缀到后缀链接处。

由于这个点内部都已经连接过了，所以只用传一个到后缀链接即可。 ::::success[看看代码]

#include<bits/stdc++.h>
using namespace std;
int n,tr[2000005][26],id,tmp[4000005],fa[2000005];
string s[2000005];
void add(string s){
    int p=0;
    for(int i=0;i<s.size();i++){
        if(!tr[p][s[i]-'a'])tr[p][s[i]-'a']=++id;
        p=tr[p][s[i]-'a'];
    }
}
int la;
struct P{
    int son[26],fail,len;
}c[4000005];
void insert(int x){
    int p=la;
    int np=la=++id;
    c[np].len=c[p].len+1;
    while(~p&&!c[p].son[x])c[p].son[x]=np,p=c[p].fail;
    if(p==-1)c[np].fail=0;
    else {
        int q=c[p].son[x];
        if(c[q].len==c[p].len+1)c[np].fail=q;
        else {
            int nq=++id;
            c[nq]=c[q];
            c[nq].len=c[p].len+1;
            c[np].fail=c[q].fail=nq;
            while(~p&&c[p].son[x]==q)c[p].son[x]=nq,p=c[p].fail;
        }
    }
}
void build(){
    id=0;c[0].fail=-1;
    queue<pair<int,int>> q;
    q.push({0,0});
    while(!q.empty()){
        pair<int,int> u=q.front();
        q.pop();
        for(int i=0;i<26;i++)if(tr[u.first][i]){
            la=u.second;
            insert(i);
            q.push({tr[u.first][i],la});
        }
    }
}
bool cmp(int x,int y){
    return c[x].len>c[y].len;
}
vector<int> e[4000005];
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)cin>>s[i],add(s[i]);
    build();
    for(int i=1;i<=n;i++){
        int p=0;
        for(int j=0;j<s[i].size();j++){
            p=c[p].son[s[i][j]-'a'];
            e[p].push_back(i);
        }
    }
    for(int i=1;i<=id;i++)tmp[i]=i;
    sort(tmp+1,tmp+id+1,cmp);
    long long ans=0;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=id;i++){
        for(int j=1;j<e[tmp[i]].size();j++){
            int x=find(e[tmp[i]][j-1]),y=find(e[tmp[i]][j]);
            if(x!=y)fa[x]=y,ans+=c[tmp[i]].len;
        }
        if(c[tmp[i]].fail)e[c[tmp[i]].fail].push_back(e[tmp[i]][0]);
    }
    cout<<ans;
    return 0;
}

::::

总结

SAM 的精髓在于同时维护了两套边。

两套边相辅相成，实现了快速的构造，空间与时间复杂度都极小。

理解 SAM 的内部结构，进而理解其构造方式，就可以帮助你快速掌握 SAM 的多种用法，许多问题也就迎刃而解了。

最后有不理解的可以私我，有空就回，有错误也可以私/评论。

最后的最后非常非常感谢管理审核。