关于后缀树的一些理解

要理解suffix tree就首先要理解Trie
还好我在刚进雅虎的时候接触到了Double Array Trie的一个具体实现
对Trie有着比较深刻的了解。
Trie的优势就是他能在o(n)时间内搜索一个长度为n的字符串s是否在字典里。
关于Trie的资料，有下面几个链接可以参考
http://www.allisons.org/ll/AlgDS/Tree/Trie/
http://linux.thai.net/~thep/datrie/datrie.html

言归正传，简单点说，后缀树就是将一个给定字符串的所有后缀全部压入一个Trie
然后将只有单个叶子的节点压缩，从而形成的一棵树
关于后缀树如何构造，有很多资料进行介绍，就不多说了
例如：
http://www.allisons.org/ll/AlgDS/Tree/Suffix/
上面这个网页里有一个手动构造后缀树的例子，非常生动

我更关注的是后缀树的用途，总结起来大概有如下几种
1. 查找字符串o是否在字符串S中。
方案：用S构造后缀树，按在trie中搜索字串的方法搜索o即可。
原理：若o在S中，则o必然是S的某个后缀的前缀。
听起来有点拗口，举个例子。例如S: leconte，查找o: con是否在S中
则o(con)必然是S(leconte)的后缀之一conte的前缀
有了这个前提，采用trie搜索的方法就不难理解了。
2. 指定字符串T在字符串S中的重复次数。
方案：用S+’$'构造后缀树，搜索T节点下的叶节点数目即为重复次数
原理：如果T在S中重复了两次，则S应有两个后缀以T为前缀，重复次数就自然统计出来了。
3. 字符串S中的最长重复子串
方案：原理同2，具体做法就是找到最深的非叶节点。
这个深是指从root所经历过的字符个数，最深非叶节点所经历的字符串起来就是最长重复子串。
为什么要非叶节点呢?因为既然是要重复，当然叶节点个数要>=2。
4. 两个字符串S1，S2的最长公共部分
方案：将S1#S2$作为字符串压入后缀树，找到最深的非叶节点，且该节点的叶节点既有#也有$(无#)。
大体原理同3

上段文字可能表达不够准确，更准确的表达可以参考
http://www.allisons.org/ll/AlgDS/Tree/Suffix/
http://blog.csdn.net/g9yuayon/archive/2008/06/21/2574781.aspx
当然英文wiki和google也是很好的参考资料~

评论

2 楼 whxtbest 2015-08-18  

whxtbest 写道

2里面：如果T本身就是重复的话   比如S是aaab，T是aa的话，这个时候是不是就有问题了

看了一下，aa应该就是aaab的最长重复子串，是允许有重叠的部分的

1 楼 whxtbest 2015-08-18  

2里面：如果T本身就是重复的话   比如S是aaab，T是aa的话，这个时候是不是就有问题了