一、为什么学后缀自动机？
Mermaid · 渲染中（下方为源码）
graph TD A[母串] --> B[在线构造 SAM] B --> C[所有子串 O(1)查询] C --> D[次数/不同子串/LCS]
后缀自动机是处理字符串子串问题的最强工具之一，能在线性空间内表示字符串的所有子串：
- 判断子串是否存在（O(|T|)）
- 统计某子串出现次数 / 不同子串个数
- 最长公共子串（LCS）
- 后缀数组、后缀树的轻量替代
对比：KMP 解决"模式匹配"，而 SAM 解决"关于母串所有子串的查询"。
二、核心概念
- 状态 (state)：代表一组 endpos 等价（在母串中结束位置集合相同）的子串
- 转移 (trans)：字符 → 下一状态
- link (后缀链接)：指向"代表当前状态所有子串的最长后缀、且 endpos 更大的状态"
- len：状态代表的最长子串长度
关键性质：不同状态数 ≤ 2n−1，转移数 ≤ 3n−4，均为 O(n)。
三、在线构造（逐字符添加）
class State {
int len, link;
int[] next = new int[26];
State() { Arrays.fill(next, -1); link = -1; }
}
State[] st = new State[2 * N];
int sz, last;
void saInit() { st[0] = new State(); sz = 1; last = 0; }
void saExtend(char c) {
int cur = sz++; st[cur] = new State();
st[cur].len = st[last].len + 1;
int p = last;
while (p != -1 && st[p].next[c - 'a'] == -1) {
st[p].next[c - 'a'] = cur; p = st[p].link;
}
if (p == -1) st[cur].link = 0;
else {
int q = st[p].next[c - 'a'];
if (st[p].len + 1 == st[q].len) st[cur].link = q;
else {
int clone = sz++; st[clone] = new State();
st[clone].len = st[p].len + 1;
st[clone].link = st[q].link;
System.arraycopy(st[q].next, 0, st[clone].next, 0, 26);
while (p != -1 && st[p].next[c - 'a'] == q) {
st[p].next[c - 'a'] = clone; p = st[p].link;
}
st[q].link = st[cur].link = clone;
}
}
last = cur;
}