「杂谈」感性理解 SAM 结构

本文主要是介绍「杂谈」感性理解 SAM 结构，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

基本参考于 EtaoinWu 的博客

因为是感性理解，重要在于对后缀树及后缀自动机结构的透彻理解。

定义：\(Left(x)\)，子串 \(x\) 在母串中出现位置左端点的集合；\(Right(x)\)，子串 \(x\) 在母串中出现位置右端点的集合。

在后缀 Trie 中：转移边链接的是自己的最长前缀，fail 边链接的是自己的最长后缀。由于所有的后缀都在其中，所以当前子串的最长前缀实际上就是除去最后一个字符剩下的串，最长后缀也类似。以此可得，正串的后缀 Trie 与反串的 fail 树是相同的。

后缀 Trie 看起来太臃肿了，考虑如何对这个 Trie 进行压缩。

类似压缩 Trie 的思想，如果一个节点只有一个儿子，那么将该节点和儿子合并。由于多一个儿子至少多一个能到达的叶子节点，那么该压缩方法实际上是按照子树内叶子节点的集合来划分等价。那么子树内叶子节点的集合相同在字符串中该如何描述？每一个叶子都代表一个后缀，所以"子树内叶子节点的集合"等价于"包含该串为前缀的原串后缀的集合"，这等价于按照 \(Left\) 来划分等价类。以此，我们得到了后缀树结构。

重新观察后缀 Trie，有一些节点子树的结构是一模一样的，那么这些节点可以合并在一起。那么子树相同在字符串中该如何描述？注意到从它开始在 Trie 里面往子孙走的路径都是走完一个后缀，也就是说这些等价类对应的子串，在原串中走到串尾都是同样的过程，这等价于它们的 \(Right\) 等价，也就是说这类压缩方式等价于按照 \(Right\) 来划分等价类。以此，我们得到了后缀自动机的结构。

观察后缀自动机上上的 fail 树（也有的地方称之为 parent 树）：注意到 \(Right\) 集合相同的子串，一定是最长的那个串的若干个长度连续的后缀，而且这个长度断开的地方，意味着这个更小的前缀 \(s\) 在其他地方出现过。假设这个等价类中最长的串的不在同一等价类的后缀 \(s\) 前面的字符是 \(c\)，则意味着母串中出现了与 \(\overline{cx}\) 不同的 \(\overline{c'x}\) 作为子串，对应在 fail 树上，就是其有多个儿子。同理，如果是在同一等价类的 \(s\)，它在母串中仅仅作为 \(\overline{cx}\) 作为子串，对应在 fail 树上，就是其仅有一个儿子。由此可以看出，后缀自动机的压缩同时是对 fail 树进行类似压缩 Trie 的压缩。

考虑到前文所说的正串的 Trie 等价于 反串的 fail，于是得到了 后缀自动机的 parent 树为反串后缀树 这一经典结论。

这篇关于「杂谈」感性理解 SAM 结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！