对 SAM 和 PAM 的一点理解

感觉自己学 SAM 的时候总有一种似懂非懂、云里雾里、囫囵吞枣、不求甚解的感觉，是时候来加深一下对确定性有限状态自动机的理解了。

1. 从 SAM 的定义上理解：SAM 可以看作一种加强版的 Trie，它可以高度压缩一个字符串的子串信息，一条从根出发到终止结点的路径对应了原串的一个后缀，而任意一个从根出发的路径对应了原串一个子串。子串和从根出发的路径一一对应。在这种的理解下，每一个结点的含义并不是固定的，它到底对应哪个子串取决于那条路径是怎么到达它的；而边有着确定的含义。

2. 从 Parent Tree 的角度去理解连边的含义：显然等价类的个数是 \(\Theta(n)\) 级别的，并且两个不同等价类的 \(\texttt{Endpos}\) 集合要么无交集，要么相包含，因此可以建出一个由 \(\texttt{Endpos}\) 集合的包含关系连结而成的树——Parent Tree，它的连边——后缀链接，若是向下看，是在一个等价类的前面加上一个字符，从而分成若干的其他等价类；向上看，它是指向包含当前集合的最小的集合；而后缀自动机的连边是在一个等价类的后面加上一个字母，看看它会指向谁，显然对于同一个添上的字母，这个指向是唯一确定的。

3. 从结点的含义去理解：虽然一个点它并不一定对应哪一个子串，但是它对应的若干子串一定有一个共同的 \(\texttt{Endpos}\)，也就是说，若长的那个存在了，短的那些一定是它的子串；短的出现了，那么它向前一些一定是那些长的。由于上面的结论，"本质"不同的子串的个数是线性的，因此我们建立这样一个自动机，其中的每一个结点都对应了一种子串。这也是为什么 Parent Tree 的结点与 SAM 的结点一一对应。

4. 关键

对 SAM 和 PAM 的一点理解

原文：https://www.cnblogs.com/Linshey/p/14219867.html