Day 153-Q2 | Suffix Array構築（Manber-Myersのダブリング法）

問題

小文字英字からなる文字列 $S$（長さ $N$）が与えられる。$S$ の全ての接尾辞（suffix）$S[i:]\ (0\le i<N)$ を辞書順に並べ替えたときのインデックス列（Suffix Array, $SA[0],\dots,SA[N-1]$）を求めよ。

入力形式

制約

$1 \le N \le 2000$

$S$ は小文字英字のみ

入出力例

入力例1

banana

出力例1

5 3 1 0 4 2

入力例2

aaa

出力例2

2 1 0

概念図：banana の接尾辞ソート

ヒント（段階的開示）

ヒント1（方向性）

$N$個の接尾辞を素朴に `sorted()` で比較すると、1回の比較に最悪 $O(N)$ かかり全体で $O(N^2\log N)$ になる。比較コストを $O(1)$ に落とす仕組みが必要。

ヒント2（アプローチ）

「長さ$k$までの接頭辞での順位（rank）」がわかっていれば、長さ$2k$までの順位は $(\mathrm{rank}[i],\mathrm{rank}[i+k])$ のペアを比較するだけで決まる（範囲外は番兵 $-1$）。これを $k=1,2,4,\dots$と倍々に増やし、$k\ge N$で全順位が確定する。

ヒント3（誘導）

def build_suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n
    k = 1
    while True:
        def key(i):
            r2 = rank[i + k] if i + k < n else -1
            return (rank[i], r2)
        sa.sort(key=key)
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i-1]] + (1 if key(sa[i-1]) < key(sa[i]) else 0)
        rank = tmp[:]
        if rank[sa[-1]] == n - 1:
            break
        k *= 2
    return sa

模範解答 (Python)

import sys


def build_suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n
    k = 1
    while True:
        def key(i):
            r2 = rank[i + k] if i + k < n else -1
            return (rank[i], r2)

        sa.sort(key=key)
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (1 if key(sa[i - 1]) < key(sa[i]) else 0)
        rank = tmp[:]
        if rank[sa[-1]] == n - 1:
            break
        k *= 2
    return sa


def main():
    s = sys.stdin.readline().strip()
    sa = build_suffix_array(s)
    print(*sa)


main()

Step-by-Step 解説

1初期状態
各文字のASCIIコードで初期rankを作る: b=98,a=97,n=110,a=97,n=110,a=97。

2k=1（接頭辞長2の比較）
$(\mathrm{rank}[i],\mathrm{rank}[i+1])$ のペアで比較し、識別力を上げていく。

3k が十分大きくなり確定
$N=6$ なので $k=1,2,4$ で十分。最終的な `sa=[5,3,1,0,4,2]` が入力例1と一致。

4計算量の確認
外側ループ $O(\log N)$ ×各回の sort $O(N\log N)$ = 全体 $O(N\log^2N)$。DC3法・SA-IS法の $O(N)$ には劣るが実装が単純。

よくあるミス

ミス	原因	正しい書き方
`rank[i+k]` の範囲外アクセスで例外	番兵処理を書き忘れる	`i+k<n` のときだけ参照、それ以外は`-1`
タイ（同順位）を区別してしまう	新rank計算のロジック誤り	直前と`key`が等しければ同じ順位番号のまま
終了条件を`k>=n`にする	早期終了・過剰継続の判定誤り	「全接尾辞のrankが相異なる」ことで判定
`key`内で`rank`を毎回コピー	余分な計算量	`rank`はループ最後に1回だけ更新
出力をカンマ区切りにする	AtCoder形式の誤解	`print(*sa)`でスペース区切り

次のステップ

発展: Kasai's Algorithmで LCP配列を$O(N)$で追加構築し、任意2接尾辞間のLCPクエリをSparse Tableで$O(1)$にする。
次回予告: 重み付き区間スケジューリング（Weighted Interval Scheduling）

自己評価

完全理解おおむね理解要復習

Day 153-Q2 — Suffix Array構築（Manber-Myersのダブリング法）

問題