后缀自动机（SAM）

Neil_Qian · 2026-08-07 09:34:52 · 算法·理论

后缀自动机

首先说明：有些证明其实是没有必要知道的，毕竟你不知道也不会妨碍你做题。更多的应该是知道这个东西是怎么被想出来的，以及怎么用的。

为什么是后缀自动机而不是前缀自动机呢？很简单，因为后缀的前缀是好处理的，前缀的后缀则没有很好的性质。

首先确定我们的目标：构建一个自动机，在自动机上从根节点开始走，可以走出所有的子串，且所有不是子串的串不会被走出来。

首先确定一个至少可行的方案：对于每个后缀建 trie 树，然后拼在一起。但是这样有 O(n^2) 个节点。

此时引入一个概念：endpos 等价类。其实没那么困难，说白了就是，如果几个字符串在原字符串中出现的位置（这里认为是右端点）相同，那么他们就在同一个等价类。举个例子，ababa 中，aba 的出现位置为 \{3,5\}，ba 的位置为 \{3,5\}，a 的位置为 \{1,3,5\}，因此 aba 和 ba 在同一个等价类，a 则不在。endpos 集合还有一个理解方式就是假装在暴力 kmp，但是每个位置同时开始，现在哪些位置还幸存。

一个简单的观察是：一个等价类中不可能有两个长度相同的串。观察上面的例子，就很容易发现一个性质：对于一个等价类，所有串长是连续的，且其它串都是最长串的后缀。第二条性质是显然的，对于第一条，考虑两个串如果长度不相邻，那么它们之间的串也会被限制，长度短的串说明没有其它匹配位置，长度长的串说明能匹配到这个位置。

继续观察，任意两个串的 endpos 集合如果相交但不包含，既然有相交那就意味着长度短的串一定是长度长的串的后缀，那么长度长的串能匹配的位置长度短的串也能匹配，应该是包含关系，矛盾。根据这个观察，可以得到 endpos 等价类会形成一个树形结构，儿子连向父亲的边表示儿子的 endpos 集合是父亲的 endpos 集合的子集。那么对于长度为 n 的串，最多会有多少个不同的 endpos 集合呢？令 f_n 表示这个答案，有 f_n=1+\max\sum_{\sum p_i=n}f_{p_i}（当然大于等于也行），如果我们声称 f_n=2n-1，显然是满足要求的。那么我们希望根据 endpos 等价类来建树，每个 endpos 集合为一个节点，来代表这些字符串。

注：如无特殊说明，以下的“父亲”指这棵树上的父亲，“儿子”指自动机上的出边。

接下来就是构造了，先放代码再来解释：（len 表示该等价类的最长串的长度，link 表示其在树上的祖先，即最小的 endpos 等价类包含它的等价类）

struct SAM{
    static const int N=2e6+10,S=28;struct Node{int len,link,ch[S];}tr[N];int cnt=1,lst=1;
    inline void insert(int c){
        int nw=++cnt,u=lst;tr[nw].len=tr[lst].len+1,lst=nw;
        while(u&&!tr[u].ch[c])tr[u].ch[c]=nw,u=tr[u].link;
        if(!u)tr[nw].link=1;
        else{
            int t=tr[u].ch[c];
            if(tr[t].len==tr[u].len+1)tr[nw].link=t;
            else{
                int nww=++cnt;tr[nww]=tr[t],tr[nww].len=tr[u].len+1,tr[t].link=tr[nw].link=nww;
                while(u&&tr[u].ch[c]==t)tr[u].ch[c]=nww,u=tr[u].link;
            }
        }
    }
}sam;