找到一個關鍵字的所有指標的後綴樹

Question

這是一個後綴樹爲輸入文本「密西西比」的視覺圖。在這個例子中，我正在搜索的關鍵字是「si」。我想我明白如何得到的「SI」

• 在根節點＃開始的第一指標1
• 第一邊緣爲「S」，所以我們旅行下來到節點＃2
• 的第二邊緣節點＃2是「我」，因此我們檢索節點＃7，並且該節點將索引存儲到文本中。

但是現在對於「si」的第二次出現......我是否繼續向下搜索子樹＃7以查找下一個出現？對我來說真的沒有意義。

或者，爲了支持多個索引，樹是否必須以不同的方式組裝？

Answer 1

問題是您在樹中沒有足夠的信息。

其導致標記6該節點的路徑表示既（通常，所有）在原來的字出現。你想要做的是當你按照算法描述的處理前綴時，你想要在節點中存儲索引。一般來說，算法不會存儲這些信息，但很容易對其進行修改。

每次訪問節點時，都要將原始字符串中的位置追加到匹配位置列表中。

1. （空樹）
2. （路徑 「SI」，節點 「6」（在附加 「6」 節點信息：4-5），樹的其餘部分）
3. 等
4. （路徑「si」，節點「6」（「6」節點中的附加信息：4-5,7-8），樹的其餘部分）
5. 等