後綴配列（Suffix Array, SA）は、ある文字列のすべての接尾辞（Suffix）を辞書順に並べた配列です。高度な文字列処理において、接尾辞木（Suffix Tree）の代替として、より省メモリで実装しやすいデータ構造として広く利用されます。

基本定義

• SA[i]: 全ての接尾辞を辞書順にソートしたとき、第 $i$ 位となる接尾辞の開始位置。
• Rank[i]: 位置 $i$ から始まる接尾辞が、辞書順で何番目かを示す順位。

これら二つには $SA[Rank[i]] = i$ および $Rank[SA[i]] = i$ という逆写像の関係があります。

倍増法による構築

接尾辞のソートを効率的に行うため、長さ $2^k$ の部分文字列をソートした結果を利用して長さ $2^{k+1}$ のソートを行う「倍増法」を用います。基数ソート（Radix Sort）を組み合わせることで、時間計算量 $O(n \log n)$ で構築可能です。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 1000005;
int suffix_idx[MAXN], rank_arr[MAXN], tmp_rank[MAXN], second_key[MAXN], buck[MAXN];

void build_sa(const string& s, int n, int m) {
    for (int i = 0; i <= m; i++) buck[i] = 0;
    for (int i = 1; i <= n; i++) buck[rank_arr[i] = s[i-1]]++;
    for (int i = 1; i <= m; i++) buck[i] += buck[i-1];
    for (int i = n; i >= 1; i--) suffix_idx[buck[rank_arr[i]]--] = i;

    for (int len = 1, p = 0; p < n; len <<= 1, m = p) {
        p = 0;
        for (int i = n - len + 1; i <= n; i++) second_key[++p] = i;
        for (int i = 1; i <= n; i++) {
            if (suffix_idx[i] > len) second_key[++p] = suffix_idx[i] - len;
        }

        for (int i = 0; i <= m; i++) buck[i] = 0;
        for (int i = 1; i <= n; i++) buck[rank_arr[second_key[i]]]++;
        for (int i = 1; i <= m; i++) buck[i] += buck[i-1];
        for (int i = n; i ≥ 1; i--) suffix_idx[buck[rank_arr[second_key[i]]]--] = second_key[i];

        memcpy(tmp_rank, rank_arr, sizeof(rank_arr));
        rank_arr[suffix_idx[1]] = p = 1;
        for (int i = 2; i <= n; i++) {
            auto is_same = [&](int a, int b) {
                return tmp_rank[a] == tmp_rank[b] && 
                       (a + len <= n ? tmp_rank[a + len] : -1) == (b + len <= n ? tmp_rank[b + len] : -1);
            };
            rank_arr[suffix_idx[i]] = is_same(suffix_idx[i], suffix_idx[i-1]) ? p : ++p;
        }
    }
}

Height配列とLCP

SA単体では用途が限られますが、Height配列（隣接するソート順の接尾辞間の最長共通接頭辞、LCP: Longest Common Prefix）を導入することで強力な力を発揮します。

$Height[i] = LCP(Suffix(SA[i]), Suffix(SA[i-1]))$

Kasaiのアルゴリズムを利用することで、$O(n)$ で構築できます。このアルゴリズムは $Height[Rank[i]] \ge Height[Rank[i-1]] - 1$ という性質を利用しています。

int h_arr[MAXN];
void build_height(const string& s, int n) {
    int k = 0;
    for (int i = 1; i <= n; i++) {
        if (rank_arr[i] == 1) continue;
        if (k) k--;
        int j = suffix_idx[rank_arr[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k - 1] == s[j + k - 1]) k++;
        h_arr[rank_arr[i]] = k;
    }
}

主な応用手法

1. 任意の2つの接尾辞のLCP

$Suffix(i)$ と $Suffix(j)$ のLCPは、Height配列の範囲最小値（RMQ）として求められます。 $LCP(Suffix(SA[i]), Suffix(SA[j])) = \min_{k=i+1}^j \{Height[k]\}$ これはSparse Table（ST表）を用いることで、前処理 $O(n \log n)$、クエリ $O(1)$ で計算可能です。

2. 異なる部分文字列の総数

文字列のすべての部分文字列は、ある接尾辞の接頭辞です。位置 $SA[i]$ から始まる接尾辞の長さは $n - SA[i] + 1$ であり、そこには $n - SA[i] + 1$ 個の接頭辞が含まれます。そのうち前の接尾辞と重複するものは $Height[i]$ 個存在するため、全体の異なる部分文字列数は以下の式で求まります。 $$\sum_{i=1}^{n} (n - SA[i] + 1 - Height[i])$$

3. 少なくともk回出現する最長の部分文字列

長さ $L$ の部分文字列が $k$ 回以上出現する場合、SA上で隣接する $k$ 個の接尾辞が $L$ 以上のLCPを持つことになります。したがって、Height配列においてサイズ $k-1$ のスライディングウィンドウ内の最小値の最大値が答えとなります。これは二分探索または単調キューで解くことができます。

4. 重なりを許さない2回出現する最長部分文字列

答えの長さ $L$ について二分探索を行います。Height配列を $Height[i] \ge L$ となる連続した区間に分割します。各区間内で、接尾辞の元の開始位置 $SA[i]$ の最大値 $max\_pos$ と最小値 $min\_pos$ を保持します。もし $max\_pos - min\_pos \ge L$ を満たす区間が存在すれば、長さ $L$ の重なり合わない部分文字列が存在すると判定できます。

実装上の注意点

• 文字種の範囲: 基数ソートの初期化時、文字コードの範囲（ASCIIなど）に合わせてバケットサイズを適切に設定する必要があります。
• 配列の添字: $SA$ や $Rank$ の計算時、配列外参照を防ぐため、文字列の末尾に最小値（'\0'など）を想定するか、十分な余白を持たせることが重要です。
• データ構造の統合: 大規模なクエリを処理する場合、Height配列に対するRMQ計算のためにSparse Tableを構築することが一般的です。