基本定义

• 对于任意字符串 $S$ ,对于其每个子串 $T$，$T$ 在 $S$ 中每次出现的右端点下标构成一个集合，称这个集合为 $T$ 的 $\text{endpos}$ 集合，所有 $\text{endpos}$ 集合相同的子串构成一个 $\text{endpos}$ 等价类。此外，空集作为一个单独的 $\text{endpos}$ 等价类。
• 后缀自动机是一个 $\text{DAG}$，图中每个点代表一个 $\text{endpos}$ 等价类。对于一条从 $u$ 到 $v$，接受字符为 $c$ 的边（下文统称 自动机边），意味着 $u$ 中所有字符串在后端添加字符 $c$ 之后都属于 $v$。
• 后缀自动机中存在另一种辅助用的边（下文统称树边）。除空集外的所有 $\text{endpos}$ 等价类有且仅有一条树边，指向该等价类所属最短的字符串删掉第一个字符后所属的等价类。显然这种边将所有节点连接成一棵树。

基本性质

• 对于任意两个字符串，若一个是另一个的后缀，则原字符串的 $\text{endpos}$ 集合是后缀字符串集合的子集

  对于原字符串每次出现，其后缀字符串一定在右端点相同的位置作为其后缀出现，可以证明该结论。

• 对于任意两个没有后缀关系的字符串，它们的 $\text{endpos}$ 集合不交

  若有交，显然在交中位置作为右端点的时候，原串会有一个位置需要填上两个不同的字符，故不交。

• 一个 $\text{endpos}$ 等价类中的所有字符串的长度是一个连续段

  考虑一个等价类中最长的字符串，不断删除首字符，直到 $\text{endpos}$ 集合变化，可以得出该结论。

定义 $n$ 为字符串 $S$ 的长度，则还有：

• $\text{endpos}$ 等价类的总数为 $O(n)$

  考虑自动机中的树边，易证一个节点的 $\text{endpos}$ 集合是它儿子集合的并，且它的儿子数大于1。因此除叶子外，每个节点都将合并至少两个集合，合并次数显然小于叶子数，而叶子数不超过字符串长度（由每个前缀对应的等价类作为叶子时最大），因此总数为 $O(n)$。

• 自动机边的总数为 $O(n)$

  对于除空集外的所有节点，定义继承边为从该节点中最长字符串去除末尾字符后所属的节点指向该节点的自动机边，显然，继承边的总数为 $O(n)$。

  我们考虑吧字符串 $S$ 的所有子串按左右端点排列成一个下三角形，并将右端点相同且属于同一 $\text{endpos}$ 等价类的子串合并起来，并连接自动机边，以ababb为例，如下图所示：

  

  其中的蓝边就是继承边，对于其他边，这些边每次都会合并两行，所以总数不超过 $O(n)$。

  特别的，对于从空集向每一列最靠上的节点连接的边，若该节点没有合并，则这是一种继承边，否则这条边实质上也是在合并两行。

  综上，自动机边的总数不超过 $O(n)$。