基于后缀树的模式搜索

给定一个文本txt[0..n-1]和一个模式pat[0..m-1]，编写一个函数搜索（char pat[]，char txt[]），在txt[]中打印所有出现的pat[]。你可以假设n>m。

预处理模式还是预处理文本？ 我们在之前的帖子中讨论了以下算法：

KMP算法 拉宾-卡普算法 基于有限自动机的算法 Boyer-Moore算法

以上所有算法都对模式进行了预处理，以加快模式搜索速度。通过预处理模式我们可以得到的最佳时间复杂度是O（n），其中n是文本的长度。在本文中，我们将讨论一种预处理文本的方法。后缀树是由文本组成的。在对文本进行预处理（构建文本的后缀树）之后，我们可以在O（m）时间内搜索任何模式，其中m是模式的长度。 想象一下你已经储存了完整的 威廉·莎士比亚 并对其进行了预处理。你可以搜索整个作品中的任何字符串，搜索时间与图案的长度成正比。这确实是一个很大的改进，因为模式的长度通常比文本小得多。 如果文本频繁更改，预处理文本的成本可能会很高。它适用于固定文本或不太频繁更改的文本。

给定文本的后缀树是给定文本的所有后缀的压缩trie .我们讨论过 标准Trie .让我们理解 压缩Trie 使用下面的单词数组。

{bear, bell, bid, bull, buy, sell, stock, stop}

以下是上述输入单词集的标准trie。

下面是压缩的trie。压缩Trie是通过连接单个节点的链从标准Trie获得的。压缩的trie的节点可以通过在节点处存储索引范围来存储。

如何为给定文本构建后缀树？ 如上所述，后缀树是所有后缀的压缩trie，所以下面是从给定文本构建后缀树的非常抽象的步骤。 1） 生成给定文本的所有后缀。 2）将所有后缀视为单个单词，并建立压缩的TIE。

让我们考虑一个示例文本“香蕉”，其中“字符串终止字符”。下面是“香蕉”的所有后缀

banana 
anana 
nana 
ana 
na 
a 
 

如果我们把上面所有的后缀都看作是单个单词，然后构建一个TIE，我们会得到下面的结果。

如果我们连接单个节点的链，我们会得到以下压缩的trie，这是给定文本“banana”的后缀树

请注意，以上步骤只是手动创建后缀树。我们将在另一篇文章中讨论实际的算法和实现。

如何在构建的后缀树中搜索模式？ 我们在上面讨论了如何构建后缀树，这是模式搜索中的一个预处理步骤。以下是在构建的后缀树中搜索模式的抽象步骤。 1) 从模式的第一个字符和后缀树的根开始，对每个字符执行以下操作。 ….. （a） 对于图案的当前字符，如果后缀树的当前节点有一条边，则跟随该边。 ….. b） 如果没有边缘，打印“文本中不存在图案”并返回。 2) 如果图案的所有字符都已处理，即给定图案的字符有一条从根开始的路径，则打印“pattern found”。

让我们将示例模式视为“Na”来查看搜索过程。下图显示了搜索“nan”或“nana”的路径。

这是怎么回事？ 文本中出现的每个模式（或者我们可以说文本的每个子字符串）都必须是所有可能后缀之一的前缀。这个陈述看起来很复杂，但它是一个简单的陈述，我们只需要举一个例子来检查它的有效性。

后缀树的应用 后缀树可以用于各种各样的问题。下面是一些著名的问题，后缀树提供了最佳的时间复杂度解决方案。 1) 模式搜索 2) 寻找最长的重复子串 3) 寻找最长的公共子串 4) 查找字符串中最长的回文

还有更多的应用程序。看见 这 更多细节。

Ukkonen的后缀树构造将在以下文章中讨论： Ukkonen后缀树构造——第1部分 Ukkonen后缀树构造——第2部分 Ukkonen后缀树构造——第3部分 Ukkonen后缀树构造——第4部分 Ukkonen后缀树构造——第5部分 Ukkonen后缀树构造——第6部分