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

我回顾了很多文献，但没有找到任何有关删除或插入到后缀树中的子字符串的信息。只有Ukkonen或McCreight的算法用于构建树。
最差的方法是在删除或插入子字符串之后重建树。但我认为这是最好的方式。
例如（位置从0开始计数）：
我有“ABCDEF”后缀树和我需要删除1至3的符号，然后我将有后缀树“AEF”。然后我需要从位置1字符串“as”添加。在此之后，我将以“aasef”为后缀树。你能帮我吗？如何从后缀树中删除子字符串？

来源

2013-05-15 user2386656

Cn你更具体吗？从我所看到的，你已经插入了字符串“abdc”，现在你想使它成为“abd”（删除子字符串）或“abced”（插入子字符串），对吧？ – ElKamina

是的，你是对的 – user2386656

你可以在更新对应后缀数组时添加/删除子串：[“Dynamic Extended Suffix Arrays”]（http://www-igm.univ-mlv.fr/~lecroq/articles/jda2009。 pdf）（pdf）。尽管如此，不能说任何后缀树。 –

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

你需要的是两件事情，第一个“后缀数组”，这将让你更多的控制搜索字符和他们的位置，第二个是“缓存算法”，这将帮助您更换。

来源

2013-05-16 09:55:50 Jegan

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

“ABCDEF”是真是小巫见大巫后缀树：

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

添加在最后一个“G”或删除“A”在开始的时候是非常容易的。

但是说我们推另一个“一”在中间：

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

我们要回去，然后从头开始检查每一个字母，看看我们是否需要插入在此基础上的一个节点。相同的，如果我们从末尾字符：

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

如果您现在插入像“EF”到最后，你必须要经过和所有的地方添加新的节点！

插入一个字符看起来像是要重新检查字符串中的每个字符，即线性时间。由于Ukkonen的算法已经花费了线性时间，因此使用任何动态插入算法都不值得，因此您应该每次都重新从头开始重新构建树，并确信它仍然非常好。

如果你不关心空间，你总是可以缓存树生成算法的每一步，那么当它在x点插入或删除的时候，只需加载树构建到点x 。

来源

2013-06-23 02:46:25 Brownbat

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

回答

相关问题