一些定理和定义就不说了史上最通俗的后缀自动机详解 - KesdiaelKen 的博客 - 洛谷博客这里都有。

我们具体说一下后缀自动机初学者难理解的地方。

什么是后缀自动机：

本质就是一个 $\tt Trie$ 树和 $\tt parent$ 树重叠的东西。

三种分类讨论怎么理解：

首先我们清楚我们加入的是一个点（字符 c ）而不是一个串，我们加入了一个点，我们通过 $\tt Trie$ 树的转移不妨设其为 $\tt trans[u][c]$ 表示在 $u$ 之后加入一个字符 c 得到的位置。

显然从空节点开始走到达某个节点 $u$ 构成一个字符串，同时也是原串的子串。

为了方便说明我们不妨设没有加入字符 c 的串是原串，加入之后为当前串。

  • 第一种情况

我们通过跳后缀链接，尝试找到是否存在原串后缀加上节点 c 得到的节点。如果不存在那么我们新加入的 c 显然是不存在的，我们直接链接根节点即可。

为什么说是不存在的，考虑直接从根节点都走一步都走不到 c。

  • 第二种情况

我们幸运地找到了当前串的后缀，不妨设节点为 $u$，而且更加幸运的是 $u$ 表示集合与 $\tt trans[u][c]$ 表示集合是连续的。也就是加入当前节点之后所表示的 $\tt endpos$ 集合都增加了 $n$ 所以我们可以直接加入。

不用更新之前节点的原因是，加入之前已经存在了 $c$ 不需要再次更新了。

我们要清楚首先 $u$ 肯定是原串的后缀，然后因为通过了 $\tt Trie$ 和最长长度的双重限制，显然 $\tt trans[u][c]$ 中只有一种长度的串，而且全部都是 $u$ 所构成的串加入了一个 $c$ 所以才可以直接加入。

  • 第三种情况

我们虽然找到了后缀，但是因为集合是不连续的，也就是不能确定 $\tt trans[u][c]$ 一定是当前串的后缀，但是其肯定存在一部分是当前串的后缀，我们考虑将其拆点，拆成两部分，一部分是满足条件 $2$ 的限制，另一部分就是剩下的了。

别忘记了我们需要更新之前后缀链接连接到更改位置的节点，那么我们需要连接到哪里呢？很简单，因为原来的点，也就是当前两个集合的并集，那么我们只要连接到深度浅的集合即可。

【模板】后缀自动机 (SAM) - 洛谷 的部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void add(int c) {
    int p = las;
    int np = las = ++ tot;
    f[np] = 1;// 这里表示当前子串出现了 1 次。
    for(; p && !d[p].ch[c]; p = d[p].fa) d[p].ch[c] = np;
    if(!p) d[np].fa = 1;
    else {
        int q = d[p].ch[c];
        if(d[q].len == d[p].len + 1) d[np].fa = q;
        else {
            int nq = ++ tot; d[nq] = d[q];
            d[nq].len = d[p].len + 1;
            d[q].fa = d[np].fa = nq;
            for(; p && d[p].ch[c] == q; p = d[p].fa) d[p].ch[c] = nq;
        }
    }
}