文字列ではなく開始位置を持つ
接尾辞配列SAは、文字列の各位置から末尾までの接尾辞を辞書順に並べた開始位置の列です。元の文字列があれば、接尾辞そのものをすべてコピーして保存する必要はありません。文字列bananaでは、a、ana、anana、banana、na、nanaの順なので、0始まりのSAは[5,3,1,0,4,2]です。配列内の位置は辞書順の順位であり、格納されている値が本文中の開始位置です。この二種類の位置を混同すると、検索結果を本文の場所として正しく返せません。
一致する接尾辞は連続区間になる
パターンanaを検索すると、SA内の接尾辞anaとananaが先頭で一致し、順位1から2の区間になります。対応する本文の位置は3と1です。本文位置の昇順で結果を返したいなら、必要に応じてその位置を別に並べ直します。二分探索でパターン以上になる下端と、パターンを接頭辞に持つ範囲の上端を求めることができます。ただし上端の比較は接尾辞全体との通常の等号だけでは表せず、パターン長までの一致をどう扱うかを仕様として定義します。
構築と検索の計算量
開始位置をn個保存する接尾辞配列自体はO(n)領域ですが、素朴に全接尾辞をコピーすると合計長はO(n²)です。比較整列で長い接尾辞を毎回先頭から比較すれば、構築時間にも大きな費用が出ます。順位を倍々に伸ばす方法などの専用構築法は、この重複比較を減らしますが、採用手法と整列方法によって上界が変わります。長さmのパターンを通常の文字比較による二分探索で探すならO(m log n)が基本的な上界であり、O(log n)回の比較を時間O(log n)と取り違えないようにします。
LCPと文字単位の注意
隣り合う接尾辞の最長共通接頭辞長を持つLCP配列を併用すると、繰り返し部分文字列などを調べやすくなります。検索の比較を減らす工夫にも使えますが、接尾辞配列だけで全ての検索が自動で最適化されるわけではありません。文字列の更新では順位が広く変わり得るので、静的な索引としての性質も考えます。番兵を加える構築法なら、番兵の順序と出力からの除外を決めます。バイト・コードポイント・照合順序によって接尾辞の並びも返す位置の単位も変わるため、正規化や言語的な辞書順は別に定義します。