接尾辞木に関するUkkonenのアルゴリズムの理解

Question

私は接尾辞木を構築するためのUkkonenのアルゴリズムに関するいくつかの作業を行っていますが、線形時間の複雑さに関する著者の説明の一部を理解していません。

私はアルゴリズムを学び、それをコード化しましたが、主な情報源として使用している論文（いくつかの部分ではちょっと混乱しています）がちょっと混乱しています。 。

助けが必要ですか？ありがとう。 Ukkonenの紙に

リンク：http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Answer 1

がGusfieldのstring algorithms textbookのコピーを検索します。それは、私が見たサフィックスツリー構築の最善の解説を持っています。線形性は、高レベルアルゴリズムのいくつかの最適化の驚くべき結果である。