接尾辞配列

文字通り、SuffixArray(以下、SAと略すこともある)は文字列の接尾辞に関係している.接尾辞:文字列内の任意の位置から末尾までのサブ列.(SAでは原列と空列が議論されている)ので、len+1個の接尾辞が共有される.接尾辞配列:文字列のすべての接尾辞からなる辞書順に小さい配列から大きい配列.SAには文字列の接尾辞が記録されているため,SAはその表す接尾辞の開始位置のみを記録する必要がある.比較辞書順はO(n)であるため,暴力アルゴリズムの複雑さはO(n^2 logn)となる.いくつかのアルゴリズムによって線形複雑度に下げることができる.ここではまず簡単なO(nlognlogn)のアルゴリズムを紹介する.
このアルゴリズムの考え方は,比較辞書シーケンスの大きさの複雑さO(n)からO(logn)を倍増法により低減することである.その解は接尾辞ではなく,長さが1のサブ列のディクショナリシーケンスサイズ配列を先に計算し,その後rank配列,すなわち,このサブ列がすべてのサブ列に並ぶ値を得た.辞書シーケンスが小さいほどrank値は小さくなります.
rank[k][i]は、開始位置iの長さkのサブストリングが、すべての長さkのサブストリングにおけるディクショナリシーケンスサイズを表す.
このとき,長さ2 kのサブストリングの大きさを比較すると,i番目の位置の長さ2 kのサブストリングの大きさはrank[k][i]とrank[k][i+k]を比較することで実現できる.
SAのsa[i]は、辞書シーケンスiの接尾辞列の開始位置を表す.

const int MAXN = 100000 + 5;
int _k, _len;
int _rank[MAXN];
int _tmp[MAXN];
int _sa[MAXN];//     。

bool _cmp(int i, int j) {
    if (_rank[i] == _rank[j]) {
        int _ri = (i+_k <= _len) ? _rank[i+_k] : -1;
        int _rj = (j+_k <= _len) ? _rank[j+_k] : -1;
        return _ri < _rj;
    } else {
        return _rank[i] < _rank[j];
    }
}

void Suffix_sa(string s, int* sa) {
    _len = s.size();

    for (int i=0; i<_len i="" sa="" _rank="" s="" _len="" for="" _k="1;" sort="" _cmp="" _tmp="" if="" copy=""/>