本文深入探讨后缀树的概念，一种特殊的字典树结构，用于高效处理字符串问题，如查找子串、计算重复次数及求最长公共子串。通过实例解析后缀树的构建过程及其在实际问题中的应用。
- 概述
后缀树，就是把一串字符的所有后缀保存并且压缩的字典树。相对于字典树来说，后缀树并不是针对大量字符串的，而是针对一个或几个字符串来解决问题。比如字符串的回文子串，两个字符串的最长公共子串等等。
性质：一个字符串构造了一棵树，树中保存了该字符串所有的后缀。
操作：就是建立和应用。
（1）建立后缀树
比如单词banana，它的所有后缀显示到下面的。0代表从第一个字符为起点，终点不用说都是字符串的末尾。
以上面的后缀，我们建立一颗后缀树。如下图，为了方便看到后缀，我没有合并相同的前缀。
前面简介的时候我们说了，后缀树是把一个字符串所有后缀压缩并保存的字典树。所以我们把字符串的所有后缀还是按照字典树的规则建立，就成了下图的样子。这就是后缀树的压缩，可见更加节省空间。
注意还是和字典树一样，根节点必须为空。 - 后缀树的应用
后缀树能解决大多数字符串的问题
（1）查找某个字符串s1是否在另外一个字符串s2中。这个很简单，如果s1在字符串s2中，那么s1必定是s2中某个后缀串的前缀。理解以下后缀串的前缀这个词，其实每个后缀串也就是起始地点不同而已，前缀也就是从开头开始结尾不定。后缀串的前缀就可以组合成该原先字符串的任意子串了。比如banana，anan是anana这个后缀串的前缀。
（2）指定字符串s1在字符串s2中重复的次数
比如说banana是s1，an是s2，那么计算an出现的次数实际上就是看an是几个后缀串的前缀。上图的a节点是保存所有起始为a字母的后缀串，我们看a字母后的n字母的引用计数即可。
（3）两个字符串S1，S2的最长公共部分（广义后缀树）
（4）最长回文串（广义后缀树）
详细介绍见博客从Trie树（字典树）谈到后缀树
后缀树（Suffix tree）
最新推荐文章于 2019-08-13 17:42:36 发布
扫一扫
1万+
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
