接尾辞ツリーを構築するための Ukkonen のアルゴリズムを使用していくつかの作業を行っていますが、線形時間の複雑さについての著者の説明の一部を理解していません。
私はアルゴリズムを学び、それをコーディングしましたが、私が主な情報源として使用している論文 (以下にリンク) は、いくつかの部分で少し混乱しているため、アルゴリズムが線形である理由がよくわかりません。
何か助けはありますか？ありがとう。
Ukkonen の論文へのリンク: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf