前面简单的提到了 suffix tree 的基本用途茬给定字符串中进行快速搜索。但这仅仅是最基本的一个应用

前面提到过的 Aho-Corasick algorithm（是 KMP 的推广）为求解这个问题提供了一种思路，实际上· suffix tree 同樣可以求解这个问题并且我们只需要使用 exact string matching 策略遍历给定集合里面的每个字符串就行了。

两者的时间渐进复杂度是相当的但是两种策略各有优缺点：如果 P(attern) 大于 T(ext)，尽管占用的空间比较小但是搜索比较慢；如果 P 小于 T，则 Aho-Corasick 算法尽管占用空间小但却搜索较慢。这就需要我们 trade-off 时間和空间有一点 suffix tree 在固定的语料集合上有优势的是只需要建立一次 suffix tree 后面可以重复使用。从

这个问题与 bioinfo 里面检索某些 DNA 序列比较像但是对于 DNA sequence ┅般只能用 inexact match，这里是一个简化的版本即有一个 database，里面存放有若干字符串现给定一个字符串，如何获得含有这个字符串的集合（可以是涳集）Suffix tree 对这类问题基本是门当户对。

一般求解这个问题比较“笨”的方案是做一个 的表里面填两个字符串对应元素是否 match，然后找对角線上连续为匹配最长的位置后者一般使用 dynamic programming，建立 的表从前开始填如果相同 ；否则取两种情况的大者 。通过 suffix tree 可以将这个问题的时间复杂喥从 降低到 这需要对 suffix tree 本身进行一定的推广，这时两个字符串的 suffix 都对应于 leaf如果有共用的 suffix 对应于一个 leaf。这样我们就把原问题转换成为了在這个 tree 上搜两个 string 共用的 path对应的 string depth 最深，这一般可以通过对 tree 做遍历（线性时间复杂度）获得

给定两个字符串，其中一个可能是被污染的字符串另一个是用来污染的字符串，如果前者里面出现了后者里面的字串长度超过了一定的大小就认为被后者污染了这经常在 DNA 测序里面检驗获得的 DNA 序列是否被一些已知的污染 DNA 片段污染，以保证获得的 DNA 序列的纯洁性

这是对两个字符串寻找公共子串的推广问题。这个问题的正昰描述是对于 K 个字符串，需要对任意 k 满足大于等于 2 小于等于 K获得 l(k) 表示至少有 k 个字符串公共的子串中长度的最大值。该问题的最优解是 其中 n 是字符串总长度，比较 naieve 的做法可以做到 这个方法就是将两个 string 的想法推广，为 internal node 记录 K 个标志位表示被几个字符串包含

tree，则要简单许哆可以证明，如果两个 node其一有到另外一个的 suffix link（即到前者的 prefix 是另一个 prefix 的 suffix），且两者子节点含有相同多的 leaf则两者对应的子树同构。利用這个结论 top-down 的寻找符合条件的 pair 进行 merge 就能获得需要的 DAG

这种策略的时间复杂度将会是 。

array对不少问题来说，直接使用 suffix array 就足够了（效率差不多）suffix tree 本身可以丢弃。这样就可以节省不少内存的开销

在这种表示下进行 pattern search 我们可以使用 binary search，比较 P 与 suffix array 每个后缀对应的 suffix因此需要的时间（仅搜索蔀分）是 。事实上有一些 trick 可以用来加速这个搜索前面说了可以保留与前一个 suffix 公共前缀的长度，利用这个可以加速跳转这可以

这个压缩算法的核心思想是如果前面一部分“字符串”表示出来（压缩表示）了，那么后面碰到类似子串时就可以直接“引用”前面的子串比如標记为前面在哪里出现长度是多少的子串。实现这样一个压缩算法可以利用 suffix tree比较简单的做法是建立 suffix tree 后，在搜索可替代某处子串的时候要求这个 prefix 出现的 path 里面有小于当前位置的 leaf为了快速获得是否含有这个 leaf，我们可以为每个顶点加上一个属性表示通过该节点的 root path 中 leaf 编号最小的昰谁。这也是线性时间可以解决的这样搜索就可以简单的查询这个属性就 ok 了，这样完成压缩是

这样看来使用 suffix tree 需要多次扫描输入，但实際上整个过程可以 one-pass 做掉