对《史上最通俗的后缀自动机详解》一文的批注

· · 算法·理论

前言

笔者在学习后缀自动机时找到了《史上最通俗的后缀自动机详解》一文。上述一文的文内有一些写的不清楚的地方，特进行批注。

本文即为对上述一文的摘选、批注文稿。

性质部分

后缀自动机的边数为 O(n)

对于模拟证明方法一部分

此时剩下 ab，到达点 3，我们还是没办法跑它跑回源点。但是，我们不一定要跑它跑回源点，只要能跑回源点就行了。于是，我们往回跑 1 到 3 的边（代表 b）。那么现在，我们就等于跑了 b+c+d=bcd 的后缀了，它是一个之后我们要跑的后缀，我们把它划掉。然后接着往回跑 abcd，连上 1 到 2 的边……

此处较绕，其实际意义为“可以将目前跑出来的后缀（即 bcd）跑回源点”。

梳理后缀自动机性质一部分：

点之间有父子关系，到达点 i 的所有字符串的长度都必然大于到达 fa(i) 的所有字符串的长度，且到达 fa(i) 的任意一字符串必为到达 i 的任意一字符串的后缀。

这一部分的父子关系是在 Parent Tree 上的，所以 fa(i) \rightarrow i 是后缀 \rightarrow 原串的关系。

性质部分的批注结束。

构造部分

后缀自动机怎么构造

在讨论在线加入字符 c 时的影响一部分：

注意一下，加入 c 后，endpos 可能发生变化的字符串只有新串的后缀（或者说，旧串的后缀加 c）（它们无论在旧串出现与否，在新串中出现的次数一定会比在旧串中多 1）。

这一部分其实挺清晰，但是还是要解释一下。

考虑旧串的子串，如果其 endpos 变化了，那么显然只能在当前变化位上变化，所以其可能增加的 endpos 一定是在 newlen 这个位置上（新串长度为 newlen，以 1 为字符串下标起点）。

归根结底，还是新串的后缀串的 endpos 发生了变化，所以只需要查后缀即可。

在讨论跳 fa(p) 循环代码一部分（对此部分的错误有修改）：

for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np;

我们进行一个循环操作。这个循环操作进行下去的条件是：!dian[p].ch[c]（p 只是防止其跳出根节点），即 p 没有一条 c 的出边。而 p 每一次循环后会跳到 dian[p].fa，即 fa(p)。

首先我们得知道往上跳到底是干什么。我们知道存在父子关系节点包含的子串有后缀关系。那么，这个 p 跳 fa(p) 操作的意思即：一个是 longest(p)（还记得 longest 是什么意思吗？定义在结论 5 的证明下面）的后缀，且与 longest(p) 所属类不同的最长串所属的类（这里的 longest 改成 shortest 也无妨）。

因为由一个节点往外连一条边就等于允许到达此节点的所有字符串往尾部添加一个新的字符。并且，由于 len(fa(i))+1=minlen(i)，因此对于 i 和 fa(i)，它们包含的子串的长度从大到小排序时也是连续的。所以我们把每一个节点想象成所有到达它的字符串的集合。那么，这个跳 fa(i) 的操作可以理解为压缩地遍历一个串的所有后缀。在这里，p=fa(p) 即从长到短遍历旧串的所有后缀。

这部分的“父子关系”依旧是建立在 Parent Tree 上的父子关系，因为父子节点是“后缀 \rightarrow 原串”的关系。

加粗部分非常关键，这里说的也挺明白的——跳 fa(p) 就是遍历后缀。

这部分之后的一段用了不少“显然”“由上面思想”一类的词语，还是不太清楚，这里根据引用内容直接引出下一段。

引用的代码部分其实就是对于旧串到新串加 c 产生的额外 endpos 进行操作（“额外”就是从来没出现过任何 endpos）。

简要地概括目的，就是“为所有不包含字符 c 转移的、S 的后缀节点（即旧串的后缀节点），添加一条指向 np 的 c 转移”。

说人话的话，就是“如果旧串某一个后缀串加 c 字符后，其在前面没出现过，那么就把这个串向 np 上连一条 c 的转移，这样在 SAM 上就出现了这么一个合法串，合法转移也就全了”。

原文后一段的大意就是如此。

但原文没提“为何有 c 转移的后缀串就不用再连一个”，有些读者就可能疑惑了。

其实本段所对应的代码根本不处理已有 c 转移的情况，遇到即停止。

SAM 要保证最小状态数原则，因此对于已有 c 转移的情况绝对不是暴力再打一个转移就行的。

原文中下面一处：

else
{
  int q=dian[p].ch[c];
  if(dian[q].len==dian[p].len+1)dian[np].fa=q;

这里声明一下停止原因，其实就是原文这句（下用加粗的方式标明重点内容）：

注意循环的终止条件。如果长度再短，这些旧串后缀加 c 形成的新字符串就已经在旧串里出现过了，显然与新串最长前缀的 endpos 不同，所以不需要继续连边。

这其实就是跳 fa(p) 为跳后缀的性质决定的。

下面这段文字比较重要：

……，我们将做一个非常有趣的判断：len(q) 是否等于 len(p)+1。这个判断是什么意思呢？因为 longest(p)+c 是新串后缀，又因为 len(q)=len(p)+1，所以 longest(q)=longest(p)+c，所以 longest(q) 是新串后缀。而 q 类中的所有串都是 longest(q) 的后缀，所以到达 q 的所有串都是新串后缀，它们的 endpos 都增加了 n，因此到达 q 的所有串的 endpos 一致，符合后缀自动机的定义。由于 q 是我们找到的第一个与 np 不同的且有后缀关系的节点，我们把 fa(np) 设为 q。

这里重新解释一下本段。

跳 fa(p) 的后缀关系自然决定了 p 类内均为旧串后缀，又因为 longest(p) 是 p 类中的最长串，因此 longest(p)+c 一定是新串后缀。

原文中，q 设为 p 的 c 出边到达的节点，len(p) 表示 p 类内的最长串长度。可知 q 其实就是 p 这一个 endpos 类中的串末尾加上 c，又因为分出的子串互异、独特，所以若 len(q)=len(p)+1，则必然有 longest(q)=longest(p)+c。

对于“……，它们的 endpos 都增加了 n”（增加在本处是不允许原来就有的）这句话，其实等价于要证明“q 类所有串在新串后缀中的存在性”和“newlen 这个 endpos 值在新串中（相比于旧串）的独特性”，这两者其实都很容易证明。

由上，我们自然就得到了文中“到达 q 的所有串的 endpos 一致”这句话了，因为原来 q 类内的 endpos 值就相同，而同步新增后当然也相同。

然后就是“符合后缀自动机的定义”很句话，这显然：一，q 类节点的 endpos 在类内依旧统一，所以 q 类依旧是 endpos 等价类；二，后缀自动机的一条 c 边是将始端节点所代表的类内串的末尾都加 c，之后得到终端节点代表的 endpos 类。

同时，我们上面构造是符合最小性要求的，所以正确。

对于“由于 q 是我们找到的第一个与 np 不同的且有后缀关系的节点，我们把 fa(np) 设为 q”这句话，该怎么看呢？可以把更小的后缀关系看成与 q 相关且已被处理，所以这部分关系在 q 合法时自然成立，先不考虑；考虑 np 的定义，就是“新串的最大前缀所属的类”，由于我们在寻找“第一个与 np 不同的且有后缀关系的节点”时，属于是由大到小地跳旧串的后缀，如果跳到 p 才有延伸出 c 边而得到的要求节点，那么比 p 长度大的旧串后缀，在加上 c 后肯定没有在先前出现过，所以这些串（指加 c 后）的 endpos 集合肯定为 {n}，也就是 np（根据定义）。所以 p，准确来说是 q，就是我们要找的点，它属于“分水岭”——比它长的后缀串不能满足性质，比它小的后缀串在它满足后缀关系时自然成立。

稀里糊涂扯了上面一大坨，其实都在说一个结论——长度大于 len(q) 的后缀串都是 np 一类的。

扯出来这么一坨结论，就可以从 Parent Tree 的角度去理解“把 fa(np) 设为 q”这个操作了。具体地，在 Parent Tree 上代表 endpos 集合的节点是充分的，即不重不漏，而 q 集合如果作为一个在旧串中就有的集合，那么其后缀集合都被处理过了（且在旧串中存在），再结合“长度大于 len(q) 的后缀串都是 np 一类的”这个结论，直接证明了 q 集合的充分性；在 Parent Tree 上的“fa(p) \rightarrow p”关系要对应“后缀 \rightarrow 前缀”关系，这个关系显然与 q\rightarrow np 的关系相同，所以 q,np 在 Parent Tree 上的关系也满足了。综上所述，“由于 q 是我们找到的第一个与 np 不同的且有后缀关系的节点，我们把 fa(np) 设为 q”这个做法是正确的。

请注意：对于上部分的讨论全在 longest(p)+c=longest(q) 的条件下进行。

接下来都是较困难的内容了。

对于下面这段：

那么，len(q)>len(p)+1 代表了什么呢？它代表了还有至少一个比 longest(p)+c 更长的串属于 q。而这个更长的串必定不是新串的后缀，因为如果是，那么去掉其最后一个字符得到的字符串必然是旧串的后缀，且其长度大于 longest(p)，因此应该先被跳到。然而事实并不是这样。所以，现在出现了一个问题：属于 q 的长度不大于 len(p)+1 的串是新串的后缀（Case 2说明过），但大于 len(p)+1 的串却不是。此时，到达 q 这个节点的字符串并不全属于一个类（准确来说，属于两个类，一类的 endpos 比另一类的 endpos 多出了一个 n），出现了问题（q 的 endpos 无法得到定义）。而现在，我们要想办法将其中一个类的子串移到另一个节点上，只保留其中一类的字符串，让 q 的 endpos 可以得到定义。

对于本段的大意进行一下重新阐发。

本段大意即为：由于 q 类的来源不单一，导致无法定义 q 的 endpos。

对于两个类的分化其实说的不太清楚，其实就是后缀串与新串非后缀子串的区别。

接下来我要重新讲一下原文中把 q 拆出含 newlen 的 nq 的过程，我认为原文算是彻底把这讲崩溃了，一塌糊涂。

首先让我们再次明确一些量：旧串 / 新串最长前缀所在类 p,np，p 类末尾加 c 后的转移类 q，把 q 拆出含 newlen 的部分后产生的 nq。

其实，SAM 的每条转移边 u --c--> v 代表一个确定性承诺：

对于 u 中的每一个字符串 x，x+c 的所有出现位置，恰好等于 v 的 endpos 集合向上追溯（沿 v 的 fa 链）能覆盖到的范围。

上面这块其实是最应该讲的，就是 SAM 的转移边的目的 / 宗旨之一，讲了这个我们才能更好的讲拆分过程。

对于我们所谓 len(q)>len(p)+1 的情况，其实就是向上追溯的路径数 / endpos 的来源不唯一，产生了许多不确定性。

此时我们需要把满足 |x|\le len(p)+1 的 q 中字符串 x 单列一个 nq 集合（新串后缀集合），来区分集合作用区间。

显然，分裂集合其实只是一种内部的分类讨论，所以 nq 的出边和 q 的应该是一致的。

那么还需要讨论一下 np,nq 的位置，注意到 nq 本质是对于原 q 集合特定区间内的数值的克隆，所以 nq\in q，所以 nq 在 Parent Tree 上的关系就应该是 fa(nq)=fa'(q),fa(q)=nq（其中 fa' 表示过往值）；由于 nq 的 endpos 包含了 n，因此 np 让 nq 当 fa 其实很合适，所以 fa(np)=nq。

关于向上跳的部分其实原文挺清楚的了，不过注意要从 p 开始跳，这样才能保证后缀性质，从而保证不会把该为 q 的指向改为 nq。

还有就是 dian[p].ch[c]==q 这个判断本身就是长度筛选器，循环在 p 的 fa 链上自动停在第一个不该改的状态，无需显式比较 len，这一点也在原文中写的很清楚了。

重新概述一下上面的 Case。

对于具体的代码实现，我们的结构体中至少要实现如下内容。

注意，在一个合法的 SAM 上，对于任意的 fa(q)=p，有 minlen(q)=len(p)+1，所以只需要记录各节点的 len 就能推导出 minlen。这是原文提到过的，在这里复述一下。

到此，“后缀自动机构造”一部分的批注内容就完结了。

应用

求 endpos 大小

这里讲一讲最重要的内容：求出每个节点 endpos 集合的大小。

原文在这里讲的很乱，所以这里重讲一下。

初始化：每个状态 v 的 f[v] = 该状态作为“某个前缀终点”的次数。

对于每个新建点 np，应该令 f[np] = 1。

那对于 Case 3 克隆的节点 nq，我们用不用令 f[nq] = 0 呢？实际上是用的，虽然我们更改了节点指向，但是原 q 点对于原集合所有串的贡献依旧存在，所以如果不更改会导致计算重复。

于是有如下操作：

累加传递：按 len 从大到小遍历所有状态，执行 f[dian[v].fa] += f[v]。

为什么这样是对的？因为一个子串的每次出现，必然对应某个前缀的结尾。每个前缀在插入时会给一个状态 +1，最终通过 fa 链向上累加，父状态就能获得所有子串的出现次数。

如下为“P3804 【模板】后缀自动机（SAM）”参考代码：

#include <bits/stdc++.h>
using namespace std;
const int M = 26, N = 1e6 + 10;

int tot = 1, lst = 1;
// int edp[N << 1];

struct SAM {
    int ch[M];
    int len, fa;
    int edp;
} sam[N << 1];

vector<int> E[N << 1];

void add(int c) {
    int p = lst, np = lst = ++tot;
    sam[np].len = sam[p].len + 1;
    sam[np].edp = 1;
    // Case 1 ---
    for ( ; p && !sam[p].ch[c]; p = sam[p].fa) sam[p].ch[c] = np;
    if (!p) { sam[np].fa = 1; return; }
    // Case 1 ---
    // ---
    // Case 2 | 3 ---
    int q = sam[p].ch[c];
    if (sam[q].len == sam[p].len + 1) {
        sam[np].fa = q;
    } else {
        int nq = ++tot;
        sam[nq] = sam[q];
        sam[nq].len = sam[p].len + 1;
        sam[nq].edp = 0;
        sam[nq].fa = sam[q].fa;
        sam[q].fa = nq;
        sam[np].fa = nq;
        for ( ; p && sam[p].ch[c] == q; p = sam[p].fa) sam[p].ch[c] = nq;
    }
    // Case 2 | 3 ---
}

char tch;
long long ans;

void dfs(int u) {
    for (auto &v : E[u]) {
        dfs(v);
        sam[u].edp += sam[v].edp;
    }
    if (sam[u].edp != 1) {
        ans = max(ans, 1ll * sam[u].edp * sam[u].len);
    }
}

string s;

signed main() {
    #ifndef ONLINE_JUDGE
        #define FILEIO "P3804_3"
        freopen(FILEIO ".in", "r", stdin);
        freopen(FILEIO ".out", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    // while (cin >> tch) {
    //     add(tch - 'a');
    // }
    cin >> s;
    for (auto &c : s) add(c - 'a');
    for (int i = 2; i <= tot; ++i) {
        E[sam[i].fa].emplace_back(i);
    }
    dfs(1);
    cout << ans << "\n";
}