Suffix automaton：识别全部子串的最小 DFA
suffix tree 一页把 text 的全部后缀叠成一棵树；NFA / DFA 与子集构造 一页给出了「一组活跃集合各当一个 DFA 状态」的子集构造思想。把这两件事结合起来，就得到 suffix automaton (SAM)——一台识别 text 全部子串的有限自动机，而且是状态最少的那一台。它的状态数与边数都只有 O(n)，却能 O(m) 回答「是不是子串 / 是不是后缀 / 出现几次」，还能 O(n) 求出本质不同子串的总数。它还支持在线 (online) 构造：一个字符一个字符喂进去，每步都维护「已读前缀」的那台最小 DFA。
状态 = endpos 等价类。 对子串 w，记 endpos(w) = 它在 text 中所有出现的结束位置的集合。把 endpos 完全相同的子串归为一个状态 (state)——同一状态里的子串，长度恰好填满一段连续区间 (len[link], len]。len
记该状态里最长子串的长度。
两种边。 转移 (transition)：读一个字符前进，构成一张 DAG（长度只增不减，无环），从 root 沿转移走出的每条路径就是 text 的一个子串。suffix link:link[v] 指向「endpos 严格更大、且最长的」那个状态，所有 suffix link
反向连成一棵树（root = 空串）。
1 · 第一步：在线构造——逐字符喂入，看状态怎么长出来
点「下一步」每次读一个字符 c：先新建整串这个新前缀的落点 cur，再从上一次的 last 沿 suffix link 链往回走，给一路上还缺 c 转移的状态补上
。回退会遇到三种情况，其中最微妙的是分裂 (clone)：某个旧状态 q 里混进了「太长」的子串，必须复制出一个长度刚好的 clone，把部分转移改道过去——这正是 SAM 保持「最小」的关键一步。
状态数为 O(n) 的原因：每读一个字符，最多新增 1 个 cur 外加至多 1 个
clone，所以状态数 ≤ 2n − 1，转移数 ≤ 3n − 4。整套在线构造均摊 O(n)（字符集为常数时）。这正是它比 suffix tree 那页更省的地方——同样能回答全部子串问题，结构却更小。
2 · 第二步：在 SAM 上查询——子串 / 后缀 / 出现次数
建好后，查一个子串就是从 root 沿转移逐字符走：走得通 = 它是 text 的子串；终点落在终止状态（整串 last 沿 suffix link 链回到 root 路过的那些）上 = 它还是 text 的后缀；而终点状态的 cnt（= 它的 endpos 集合大小，沿 suffix link
树自底向上累加得到）就是 pattern 的出现次数。
本质不同子串数可以直接读出。 每个状态 v 恰好「新带来」
个之前没见过的子串（就是它独占的那段长度区间）。把所有状态加起来 Σ (len[v] − len[link[v]]) 就是 text 的本质不同子串总数——一次遍历 O(n)。上面读数里的 distinct 就是这么来的。
与相邻页的关系：它和 suffix tree 是「一体两面」：把 reverse(text) 的 SAM 的 suffix link 树反转，正是原串的 suffix tree。它也是 NFA / DFA 与子集构造 一页思想的延伸——识别的不是单个 pattern，而是全部子串的最小 DFA。想进一步「找出所有出现位置」（Aho-Corasick、suffix tree 能做的）：给每个非 clone 状态记下它的那个 endpos，再沿 suffix link 树把子树里的位置收集上来即可。