在由Ukkonen算法构造的隐式后缀树中搜索
我遇到了一个需要一个数据结构的问题，该数据结构将包含一个字符串S并允许我：
我想通过Ukkonen算法构建的后缀树是我正在寻找的。 算法被描述为“后缀树的在线构建”，并且我在“在线”部分存在问题：在插入每个字符算法之后构造隐式后缀树，其可以在最后一步中转换为显式。 但是如果我想在该步骤之前使用隐式树进行搜索呢？ “在线”表明，在插入任何已分析字符串的前缀后，可能会出现这种情况，但我找不到任何甚至可以在隐式树上运行的最简单算法的例子。
我的问题是：如何在隐式后缀树中搜索字符串？
编辑：我接受了一个很好的答案，解决了我的问题，但同时我设法找出了一个简单的解决方案2：它只需要搜索U的后缀S的长度| U | 使用KMP算法，最后匹配的字符数将是字符串重叠。
隐式后缀树和显式后缀树之间只有一个区别：它不包含字符串末尾标记（并且不包含与这些末尾字符串标记对应的任何分支）。
这意味着在隐式后缀树或明确后缀树中搜索子字符串的位置没有区别。 由于隐式后缀树含有较少的不必要分支，因此可以保证子字符串搜索更高效（但仍然是线性时间）算法。
因此需求＃1自动满足：只需从根目录搜索后缀树并选择与给定字匹配的分支。
至于需求＃2，我认为，你不能用相同的隐式后缀树来满足它。 因为你需要结束标记来处理后缀。
但是你可以在O(|U|)时候用给定单词U单独（显式）后缀树来完成它。 诀窍是在构造后缀树之前将这个单词逆转。 要找到S的最长后缀（也是U的前缀），请使用此单独的后缀树来查找反向字符串S的最长前缀，该字符串也是反向字符串U的后缀。 只需从根目录搜索此后缀树，选择与反向字符串S匹配的分支，并记住带有字符串结束标记的最新节点。 然后在从根节点到此节点的路径上反转字符串（或者确定此路径的长度并从S的尾部复制长度相同的子字符串）。
上一篇: Search in implicit suffix tree constructed by Ukkonen algorithm