文字列 T[0..n] に対する部分文字列 P[0..m] の探索を O(m lg n) で可能とするデータ構造。
文字列 T[0..n] における全部分文字列の出現位置を配列 SA[0..n] に保持し、SA を T に対して辞書式順にソートした配列 (接尾辞配列 = Suffix Array) を利用する。
例として "abracadabra" という文字列を考える。abracadabra の部分文字列の出現位置を列挙すると
0 => abracadabra 1 => bracadabra 2 => racadabra 3 => acadabra 4 => cadabra 5 => adabra 6 => dabra 7 => abra 8 => bra 9 => ra 10 => a
となる。この出現位置を、辞書式順にソートする
10 => a 7 => abra 0 => abracadabra 3 => acadabra 5 => adabra 8 => bra 1 => bracadabra 4 => cadabra 6 => dabra 9 => ra 2 => racadabra
ソートの結果得られた [ 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2 ] という配列が SA である。"abracadabra" に対する部分文字列検索は、SA と元テキストを使った二分探索により実装できる。
Suffix Array を利用すると部分文字列を高速に検索することができるが
という二点の課題がある。この課題を解決するための方法はこれまで様々なものが提案されており、前者に対しては Suffix Array に特化したソートアルゴリズム、後者に対しては圧縮全文索引などを利用するなどの手法が提案されている。