Ukkonen的後綴樹算法，有什麼必要？

這是一個很好的算法解釋，但它不是算法本身，而是殺死我，而是用來實現它的數據結構。

我需要的數據結構儘可能小和儘可能快，我見過許多實現只使用節點，一些只有邊緣，一些有邊緣和節點等等。然後有變化，一個網站我是閱讀聲稱一個節點不需要有一個指向其父節點的指針，而其他地方沒有考慮節點的子節點是如何管理的。

我的想法是使用int start和int * end（指向當前結束或階段i）的節點結構。每個節點都有一個後綴鏈接指針，一個指向其父節點的指針，以及一個指向包含其子節點的向量的指針。

我的問題是，這些東西是否足以實現後綴樹？我能以任何方式最小化它嗎？我還沒有看到嚮導中的孩子的實現，所以我對我自己的想法持懷疑態度。有人能解釋一下用這種方式只用節點來實現一個後綴樹需要什麼？

2014-09-26 E.Cross

數組就一個側面說明，也看看後綴數組。據說它們實施起來要容易得多。 – 2014-09-26 17:48:22

當我必須實現該算法時，更好的解釋文檔是原始的Ukkonen paper，並且有一個newer with images。

是的，在這些文件中都是內部實現Ukkonen的後綴樹算法。

2014-09-26 18:30:17 NetVipeC

下面可能會有所幫助：

在這裏，我們有
1.起點，終點代表邊標籤
2.後綴鏈接
3.兒童

2015-02-08 12:00:27

回答