未完成，施工中
SAM – Suffix Automation (Smallest DFA)
Also is DAG – Directed Acyclic Graph
Vertex – State Edge – Transformer
SAM 是一张有向无环图。结点被称作[[State – 状态]]，边被称作[[状态]]间的[[转移]]。
图存在一个源点 t_0，称作[[Initial State – 初始状态]]，其它各结点均可从 t_0 出发到达。
每个 [[转移]] 都标有一些字母。从一个结点出发的所有[[转移]]均不同。
存在一个或多个[[End State – 终止状态]]。如果我们从初始状态 t_0 出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是字符串 s 的一个后缀。
s 的每个后缀均可用一条从 t_0 到某个终止状态的路径构成。
在所有满足上述条件的自动机中，SAM 的结点数是最少的。
t_0 – Ground Zeros (Initial Vertex)
线性时间内通过 SAM 解决
- 在另一个字符串中搜索一个字符串的所有出现位置
- 计算给定的字符串中有多少个不同的子串
SAM 将给定字符串的所有子串以高度压缩的形式储存
对于一个长度为 n 的字符串，它的空间复杂度仅为 O(n)。 此外，构造 SAM 的时间复杂度仅为 O(n)。
准确地说，一个 SAM 最多有 2n-1 个节点和 3n-4 条[[转移边]]。 (转移边的端点可能会改变)
给定 k 个字符串 找到它们的最长公共子串 – 作为子串出现在每个字符串中的字符串
需要计算可达性 – 对于自动机中的每个状态和每个字符 D_i，是否存在这样的一条路径。可以容易地通过 DFS 或 BFS 及动态规划计算
将所有的子串连接成一个较长的字符串 T，以特殊字符 D_i 分开每个字符串（一个字符对应一个字符串） \(T = S_1 + D_1 + S_2 + D_2 + .. + S_k + D_k\)
对字符串 T 构造后缀自动机 如果 S_j 包含了一个子串，则 SAM 中存在一条从包含字符 D_j 的子串 而不包含以其它字符 D_1, …, D_j-1, D_j+1, …, D_k 开始的路径