Summary:

1. s 的字串可以依据所有在原串中的结束位置集合 right 划分为多个等价类。
2. SAM 由初始状态 t_0 和每一个 right 等价类对应的每个状态组成。
3. 对于一个状态 v ，记 longest(v) 表示对应等价类中最长子串，len(v) 为其长度，shortest(v) 表示其中最短字串，minlen(v) 为其长度。 那么这个状态对应的所有字符串均为 longest(v) 的后缀，长度在 [minlen(v), len(v)] 之间。
4. 对于任意不是 t_0 的状态 v ，定义后缀链接 link(v) 表示连接到对应字符串 longest(v) 的长度为 minlen(x) - 1 的后缀的一条边。从根节点 t_0 出发的后缀链接可以构成一棵树。这棵树表示了 right 的包含关系。
5. 如果我们从任意状态 v_0 开始顺着后缀链接遍历，总会到达初始状态 t_0 这种情况下我们可以得到许多 [len(v_i), minlen(v_i)] 的序列，且他们的并集形成了连续的区间 [0, len(v_0)].