algorithm - 在 Ukkonen 算法构造的隐式后缀树中搜索

Question

我遇到了一个问题，它需要一个数据结构来保存字符串 S 并允许我:

1. 在 O(|W|) 时间内检查词 W 是否是 S 的子词
2. 在 O(|U|) 时间内找到同时也是给定单词 U 前缀的 S 的最长后缀
3. 在 O(|K|) 时间内在 S 的末尾追加字符串 K

我发现 suffix trees由 Ukkonen 算法构造的是我正在寻找的。算法描述为 "On-line construction of suffix trees" ，我对“在线”部分有疑问:在插入每个字符算法后构造一个隐式后缀树，可以在最后一步将其转换为显式。但是，如果我想在该步骤之前使用隐式树进行搜索怎么办？ “在线”表明在插入分析字符串的任何前缀之后是可能的，但我找不到任何在隐式树上运行的最简单算法的例子。

我的问题是:如何在隐式 后缀树中搜索字符串？

编辑:我接受了一个很好的答案来解决我的问题，但与此同时我设法找到了一个更简单的解决方案 2:在长度为 |U| 的 S 后缀中搜索 U 就足够了使用KMP算法，最后匹配到的字符数为字符串重叠。

Answer 1

隐式后缀树和显式后缀树只有一个区别:它不包含字符串结束标记(并且不包含与这些字符串结束标记对应的任何分支)。

这意味着在何处搜索子字符串没有区别 - 在隐式后缀树中还是在显式后缀树中。由于隐式后缀树包含更少的不必要分支，这保证了更有效(但仍然是线性时间)的子字符串搜索算法。

因此自动满足要求 #1:只需从根搜索后缀树并选择与给定单词匹配的分支。

至于要求 #2，我认为，您无法使用相同的隐式后缀树来满足它。因为您需要字符串结尾标记来处理后缀。

但是您可以在 O(|U|) 时间内为给定的单词 U 使用单独的(显式)后缀树。诀窍是在构建后缀树之前反转这个词。要查找同时也是 U 前缀的 S 的最长后缀，请使用此单独的后缀树来查找反转字符串 S 的最长前缀> 这也是反转字符串 U 的后缀。只需从根开始搜索这棵后缀树，选择与反转字符串 S 匹配的分支，并记住带有字符串结束标记的最新节点。然后将根节点到该节点的路径上的字符串进行反转(或者确定这条路径的长度，从S的尾部复制相同长度的子字符串)。