用途
略。
根本思想
略。
概念阐释
-
endpos：这是一个集合。\(endpos(x)\) 代表子串 \(x\) 在 \(s\) 中所有结束位置的集合。
-
等价类：这也是一个集合。一个等价类中包含所有 \(endpos(i)\) 完全相等的子串 \(i\)。
有如下引理（其实很显然，看了理解了就可以了）：
-
同一等价类中，子串绝对存在后缀包含关系。
-
若子串 \(u\) 为子串 \(v\) 的后缀，\(endpos(u)\) 被包含于 \(endpos(v)\)；否则二者的 \(endpos\) 无交。
-
同一等价类中，串的长度绝对连续，且没有重复。
接下来是有关 SAM 构建的概念。
-
SAM 本身：和其他自动机一样，以字典树结构为主体。
-
SAM 中的节点：代表一个等价类。或者说，它在字典树中所处的位置代表着该等价类中的最长字串，下文将该字串记为 \(w\)。
-
原点：代表空串的节点 0。
-
len：每个节点上储存的数据。代表 \(w\) 的长度。
-
后缀链接（link）：每个节点上储存的数据，类似其它自动机的 fail。它指向 \(w\) 最长的一个后缀，which 满足不在该等价类中。容易发现，后缀链接可构成一棵以 0 为根的树。
-
转移边：就是普通字典树边，储存字符信息。