21、后缀树
后缀树(Suffix tree)是一种数据结构,能快速解决很多关于字符串的问题。后缀树提出的目的是用来支持有效的字符串匹配和查询。
学习后缀树之前,先了解一下Trie这个数据结构Trie是一种搜索树,可用于存储并查找字符串。Trie每一条边都对应一个字符。在Trie中查找字符串S时,只要按顺序枚举S的各个字符,从Trie的根节点开始选择相应的边走,如果枚举完的同时恰好走到Trie树的叶子节点,说明S存在于Trie中。如果未到达叶子节点,或者枚举中未发现相应的边,则S没有被包含在Trie中。
后缀树就是一种压缩后的Trie树。
比如 S:banana,对S建立后缀树。
首先给出S的后缀们
0:banana
1:anana
2:nana
3:ana
4:na
5:a
6:空
为了更清楚的表示后缀,我们在后缀的后面加上$
0:banana$
1:anana$
2:nana$
3:ana$
4:na$
5:a$
6:$
然后对其进行分类:
5:a$
3:ana$
1:anana$
0:banana$
4:na$
2:nana$
6: $
后缀树的应用:
example 1:在树中查找an(查找子字符串)
example 2:统计S中出现字符串T的个数
每出现一次T,都对应着一个不同的后缀,而这些后缀们又对应着同一个前缀T,因此这些后缀必定都属于同一棵子树,这棵子树的分支数就是T在S中出现的次数。
example 3:找出S中最长的重复子串,所谓重复子串,是指出现了两次以上。首先定义节点的“字符深度” = 从后缀树根节点到每个节点所经过的字符串总长。找出有最大字符深度的非叶节点。则从根节点到该非叶节点所经过的字符串即为所求。
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。