連結リスト上の Suffix Tree

ふつうの Suffix Tree は、文字列のランダムアクセス性を仮定している。

でも、いま考えている選択的アルファベット拡大（文字の連結によるアルファベットへの新文字追加）を
行うには、配列よりも連結リストの方が都合がいい。
連結リストではランダムアクセスはできない。

ランダムアクセスが必要になるのは、構築時、
枝のスキップや分岐ノードの作成を行うとき。

枝のスキップは、存在すると分かっている部分文字列に関して、マッチングをせずに、
ただ先のノードに進むこと。
これに関しては、枝の長さを別に保持しておけばよい。

分岐ノードの作成のときには、
「枝のラベルの開始位置から3文字目」のような形で分岐位置を指定する。
ランダムアクセス可能ならば、その位置が即座に分かるが、
連結リストの場合は、３つめの要素へのポインタは、実際に３つたどらないと分からない。

最悪計算時間は枝の最大長のオーダー。
ただし、ふつうは枝はあまり長くない。
長い枝は、（文脈によって区別される）ながいユニークな部分文字列にあたる。