使用Ukkonen算法构建的隐式后缀树中进行搜索

Question

我遇到了一个问题，需要一个数据结构来保存字符串S，并允许我进行以下操作：

1. 在O（|W|）时间内检查单词W是否为S的子串
2. 在O（|U|）时间内找到S的最长后缀，该后缀也是给定单词U的前缀
3. 在O（|K|）时间内将字符串K附加到S的末尾

我发现由Ukkonen算法构建的{{link1：后缀树}}正是我正在寻找的。该算法的描述为{{link2：“后缀树的在线构建”}}，我对“在线”部分有疑问：在插入每个字符后，算法构造一个隐式的后缀树，可以在最后一步将其转换为显式的。但是如果我想在此步骤之前使用隐式树进行搜索怎么办？ “在线”表明在分析字符串的任何前缀后插入后，可以进行搜索，但我找不到任何操作隐式树的最简单算法的示例。

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

编辑：我接受了一个非常好的答案来解决我的问题，但同时我设法找到了一个更简单的解决方案2：只需要使用KMP算法在长度为|U|的S后缀中搜索U，并且最后匹配字符数将是字符串重叠。

- KCH

Answer 1

只有一点差异将隐式后缀树和显式后缀树区分开来：它不包含字符串末尾标记（也不包含与这些字符串末尾标记相对应的任何分支）。

这意味着在哪里搜索子字符串- 在隐式后缀树中还是在显式后缀树中都没有区别。由于隐式后缀树包含较少的不必要分支，这保证了更高效的（但仍为线性时间）子字符串搜索算法。

因此，要满足第一个要求：只需从根节点开始搜索后缀树，并选择与给定单词匹配的分支。

至于第二个需求，我认为您不能使用相同的隐式后缀树来满足它。因为你需要字符串末尾标记来处理后缀。

但是，可以使用给定单词U的单独（显式）后缀树以O(|U|)的时间完成它。窍门是在构建其后缀树之前反转该单词。要查找字符串S的最长后缀，该后缀也是字符串U的前缀，请使用此单独的后缀树查找反转字符串S的最长前缀，该前缀同时也是反转字符串U的后缀。只需从根节点开始搜索此后缀树，选择与反转字符串S匹配的分支，并记住带有字符串末尾标记的最新节点。然后在根节点到此节点的路径上反转字符串（或确定此路径的长度并从S的尾部复制相同长度的子字符串）。

- Evgeny Kluev