algorithm - 如何从后缀树中删除子字符串？

Question

我查阅了很多文献，但我没有找到任何关于将子字符串删除或插入到后缀树中的信息。只有 Ukkonen 或 McCreight 的算法用于构建树。
最糟糕的方法是在删除或插入子字符串后重建树。但我认为这是一种最好的方法。
例如（位置从 0 开始计算）：
我有带有“abcdef”的后缀树，我需要删除从 1 到 3 的符号。然后我将拥有带有“aef”的后缀树。然后我需要从位置 1 添加字符串“as”。在此之后，我将拥有带有“aasef”的后缀树。你能帮助我吗？

Answer 1

您在问题中混合了两个任务，首先搜索字符，然后替换字符。后缀树的第一部分为您搜索字符，现在您需要第二种算法来用新字符替换该字符。随着字符被替换，原始后缀树变得无效，因此必须再次映射树以进行第二次替换。

您需要的是两件事，首先是“后缀数组”，它可以让您更好地控制搜索字符及其位置，其次是“缓存算法”，它可以帮助您进行替换。

Answer 2

我才刚刚开始使用后缀树，所以我可能错了，但似乎插入或删除可以以非常激进的方式改变树。

“abcdef”是一个非常简单的后缀树：

abcdef
├a..$
├b..$
├c..$
├d..$
├e..$
└f$

在末尾添加“g”或在开头删除“a”非常容易。

但是假设我们在中间加上另一个“a”：

abcadef
├a
│├b..$
│└d..$
├b
├c
├...

我们必须回去检查从头开始的每个字母，看看是否需要基于此插入一个节点。如果我们最后有一个字符，则相同：

abafef
├a
│├bafef$
│└fef$
├bafef$
├f
│├ef$
│└$
└ef$

如果您现在在末尾插入类似“ef”的内容，则必须遍历并在整个地方添加新节点！

插入一个字符看起来会涉及重新检查字符串中的每个字符，即线性时间。由于 Ukkonen 的算法已经花费了线性时间，因此使用任何动态插入算法都不值得，您应该每次都从头开始重新生成树，并确信这仍然相当不错。

如果您不关心空间，则可以始终缓存树生成算法的每个步骤，然后在点 x 处插入或删除时，只需将树加载到点 x 为止。