接尾辞配列 (Suffix Array)

SA :
LCP :
SA^-1 :

定義

文字列wの接尾辞を，辞書式順序に並べ直したときの，接尾辞番号を配列として保存したもの．

構築アルゴリズム

素朴な手法 /Scripts/Python/SA.py

LarssonSadakane法

参考文献

N.J.Larsson and K.Sadakane. Faster suffix sorting. Technical report LU-CSTR:99-214, Dept. of Computer Science, Lund University, Sweden, 1999.