2011年软考程序员考试复习笔试知识点整理(17)

 　　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中最长的重复子串，所谓重复子串，是指出现了两次以上。首先定义节点的"字符深度" = 从后缀树根节点到每个节点所经过的字符串总长。找出有最大字符深度的非叶节点。则从根节点到该非叶节点所经过的字符串即为所求。