看动画学算法系列之:后缀树suffix tree

简介

字典树trie

压缩字典树

后缀树suffix tree

后缀树的搜索

查找最长重复子字符串

查找两个字符串的最长公共子字符串

后缀树的代码实现

模式匹配是一个在工作中经常会用到的场景，比如说给定一个字符串数组txt[0…n-1]和要匹配的模式pat[0…m-1]，我们希望找出所有在txt中能够匹配模式字符串的次数。这就叫做模式匹配。

要想完成字符串匹配的任务，我们其实有两种方式，第一种方式就是使用各种模式匹配的算法，比如kmp，rabin karp，finite automata based和boyer moore。 这些匹配算法最好的时间复杂度是o(n)，其中n是字符串的长度 。

还有一种方式是对要查询的字符串数组进行预处理，处理过后再进行匹配的话，时间复杂度可以减少到o(m)，其中m是要匹配的模式的长度。

实际上这就是空间换时间的概念，假如我们有一本康熙字典，即使是o(n)的时间复杂度也住够长了，如果能够进行预处理之后，o(m)的时间复杂度将会大大减少我们的搜索时间。

那么是不是所有的字符串的模式匹配都可以使用预处理呢？

当然不是，因为预处理是需要耗费时间的，预处理的情况只适用于一次