从trie树谈到后缀树
3星 · 超过75%的资源 需积分: 10 157 浏览量
2013-03-14
14:07:55
上传
评论
收藏 479KB DOCX 举报 
引言
常关注本 的读者朋友想必看过此篇文章：从
B
树、 B+ 树、 B* 树谈到
R 树 ，
这次，咱们来讲另外两种树： 树与后缀树。不过，在此之前，先来看两个问
题。
第一个问题： 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频
繁出现的前 个词，请给出思想，给出时间复杂度分析。
之前在此文：海量数据处理面试题集锦与
Bit-map
详解 中给出的参考答案：用
树统计每个词出现的次数，时间复杂度是 （ 表示单词的平均长度），
然后是找出出现最频繁的前 个词。也可以用堆来实现（具体的操作可参考第三
章、寻找最小的
k
个数 ），时间复杂度是 。所以总的时间复杂度，是
与 中较大的哪一个。
第二个问题：找出给定字符串里的最长回文。例子：输入 。则输出
。这道题的流行解法是用后缀树（，但其用途远不止如此，
它能高效解决一大票复杂的字符串编程问题（当然，它有它的弱点，如算法实现
复杂以及空间开销大），概括如下：
查询字符串 是否包含子串 。主要思想是：如果 包含 ，那么 必定是
的某个后缀的前缀；又因为 的后缀树包含了所有的后缀，所以只需对 的后
缀树使用和 相同的查找方法查找 即可（使用后缀树实现的复杂度同流行
的 算法的复杂度相当）。
找出字符串 的最长重复子串 。比如 里 同 都重复出现，
而最长重复子串是 。
找 出字符串 同 ! 的最长公共子串。注意最长公共子串（"#
$%%#）和最长公共子序列（"#$%%
#&'"$）的区别：子串（#）是串的一个连续的部分，子
序列（#&）则是从不改变序列的顺序，而从序列中去掉任意的元素
而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子
序列 "$）则不必。比如字符串 同 ( 的最长公共子串为 ， 而他们
的最长公共子序列是 。"$ 可以使用动态规划法解决。
)*+"%, 无损压缩算法。 ")- 算法的基本原理是利用编码数据本身存在字符
串重复特性来实现数据压缩，所以一个很好的选择是使用后缀树的形式来组织存
储字符串及其对应压缩码值的字典。
找出字符串 的最长回文子串 。例如： 的最长回文子串是
（此即为上面所说的第二个问题：最长回文问题，本文第二部分将详细
阐述此问题）。
多模式串的模式匹配问题。（#./01二分）。
剩余26页未读，继续阅读
评论2
最新资源