如何從後綴樹中刪除子字符串？

我回顧了很多文獻，但沒有找到任何有關刪除或插入到後綴樹中的子字符串的信息。只有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

如何從後綴樹中刪除子字符串？

回答

相關問題