3

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

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

我发现由 Ukkonen 算法构建的后缀树是我正在寻找的。算法被描述为“后缀树的在线构建”，我对“在线”部分有一个问题：插入每个字符后，算法构造一个隐式后缀树，可以在最后一步转换为显式。但是如果我想在这一步之前使用隐式树进行搜索呢？“在线”表明在插入分析字符串的任何前缀之后是可能的，但我找不到任何在隐式树上运行的最简单算法的示例。

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

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

4

1 回答 1

3

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

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

所以要求＃1 自动满足：只需从根搜索后缀树并选择与给定单词匹配的分支。

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

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

于 2013-01-11T11:39:01.803 回答