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

前言

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

性质部分

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

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

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

构造部分

后缀自动机怎么构造

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

CPP

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)$ 即从长到短遍历旧串的所有后缀。

CPP

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

$p$ 在第一个有 $c$ 边的祖先停下了（停止原因已在上文说明）。

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

……，我们将做一个非常有趣的判断：$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$。

那么，$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$ 可以得到定义。

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

• Case 1：从旧串最长前缀的 $endpos$ 类 $p$ 一直向上跳，对每个跳到的点都连指向 $np$ 的边，直到不满足无 $c$ 出边的条件。
• Case 2：跳到第一个有 $c$ 出边的 $endpos$ 类 $p'$ 后，记该节点通过 $c$ 边后到达类 $q$，如果 $len(q)=len(p')+1$，则将新串最长前缀所在 $endpos$ 类的父节点 $fa(np)$ 设为 $q$。
• Case 3：在 Case 2 的基础上，如果 $len(q)>len(p')+1$，那么将 $q$ 类中的新串后缀串分离出单独的 $nq$，从而实现管辖的分离，使 SAM 维持性质。具体地，还要令 $fa(nq)=fa'(q),fa(q)=nq,fa(np)=nq$（其中 $fa'$ 表示过往值）。

• $ch[26]$：表示出边数组（类似 Trie）。
• $len$：表示节点 $endpos$ 类的字符串长度最大值。
• $fa$：该点在 Parent Tree 上的父节点。

应用

求 $endpos$ 大小

• Case 1 新建的叶子节点 $np$：$f[np] = 1$（因为 $np$ 代表了一个新前缀，这个前缀在当前位置出现了一次）。
• Case 3 克隆的节点 $nq$：$f[nq] = 0$（克隆节点不代表新前缀）。

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#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";
}