Day 123-Q2 — サフィックス配列による暗黙的サフィックス木（LCEクエリ）

2026-08-15 赤色 Master / Phase 8+ ★★★★★★★★★ 文字列アルゴリズム・SA + LCP + RMQ

問題

文字列 $S$（長さ $N$）が与えられる。$Q$ 個のクエリが与えられ、各クエリ $(i, j)$ に対して、接尾辞 $S[i:]$ と $S[j:]$ の最長共通接頭辞の長さ（LCE, Longest Common Extension）を求めよ。

入力形式

N Q
S
i_1 j_1
...
i_Q j_Q

制約

$1 \le N \le 200000$
$1 \le Q \le 200000$
$S$ は英小文字のみ
$0 \le i_k, j_k < N$（0-indexed）

入出力例

入力例1

6 3
banana
1 3
0 2
1 1

出力例1

3
0
5

(1,3): "anana" vs "ana" → "ana"共通(3) / (0,2): "b" vs "n"不一致(0) / (1,1): 同じ接尾辞(N-1=5)

概念図: SA+LCP+RMQによるLCE

"banana" の SA と LCP 配列 rank SA suffix LCP(rank-1,rank) 05a- 13ana1 21anana3 30banana0 44na0 52nana2 クエリ (i=1, j=3) rank[1]=2, rank[3]=1 区間 [min+1, max] = [2,2] RMQ(lcp[2..2]) = lcp[2] = 3 → LCE(1,3) = 3 "anana" vs "ana" = "ana" LCP配列の区間最小値 = サフィックス木上の2葉のLCAの深さ（暗黙的木構造） Sparse TableでO(1)クエリ・Ukkonen法を使わず同等の情報量を実現

ヒント（段階的開示）

ヒント1: 方向性
愚直に先頭から比較すると1クエリO(N)、Q個で O(NQ)。明示的サフィックス木を構築しLCAを求めるのが理論的に直接的だが、Ukkonenのオンライン構築アルゴリズムは実装がかなり複雑。
ヒント2: アプローチ
実務でよく使う代替は「サフィックス配列（SA）+ LCP配列」の組み合わせ。明示的な木を作らずサフィックス木を暗黙的に表現できる。$S[i:]$と$S[j:]$のランクを$r_i,r_j$（$r_i<r_j$）とすると、LCE$(i,j)$ = LCP配列の区間$[r_i+1,r_j]$の最小値になる。
ヒント3: 誘導（コード骨格） 
def build_suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while True:
        key = lambda i: (rank[i], rank[i+k] if i+k < n else -1)
        sa.sort(key=key)
        tmp = [0]*n
        for idx in range(1, n):
            tmp[sa[idx]] = tmp[sa[idx-1]] + (1 if key(sa[idx-1]) < key(sa[idx]) else 0)
        rank = tmp
        if rank[sa[-1]] == n - 1:
            break
        k <<= 1
    return sa, rank

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    S = data[idx].decode(); idx += 1
    n = N

    # --- Step1: サフィックス配列の構築（ダブリング法） ---
    sa = list(range(n))
    rank = [ord(c) for c in S]
    k = 1
    while True:
        def key(i):
            return (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
        tmp = [0] * n
        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 <<= 1

    # --- Step2: Kasaiのアルゴリズムで LCP 配列を構築 ---
    lcp = [0] * n
    h = 0
    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and S[i + h] == S[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h > 0:
                h -= 1
        else:
            h = 0

    # --- Step3: Sparse Table（RMQ） ---
    arr = lcp[1:]
    m = len(arr)
    if m == 0:
        st, LOG = [], [0]
    else:
        LOG = [0] * (m + 1)
        for i in range(2, m + 1):
            LOG[i] = LOG[i // 2] + 1
        K = LOG[m] + 1
        st = [arr[:]]
        for kk in range(1, K):
            prev = st[-1]
            half = 1 << (kk - 1)
            length = m - (1 << kk) + 1
            if length <= 0:
                break
            st.append([min(prev[i], prev[i + half]) for i in range(length)])

    def query_min(l, r):
        length = r - l + 1
        kk = LOG[length]
        return min(st[kk][l], st[kk][r - (1 << kk) + 1])

    out = []
    for _ in range(Q):
        i = int(data[idx]); idx += 1
        j = int(data[idx]); idx += 1
        if i == j:
            out.append(str(n - i))
            continue
        ri, rj = rank[i], rank[j]
        if ri > rj:
            ri, rj = rj, ri
        out.append(str(query_min(ri, rj - 1)))

    print('\n'.join(out))

solve()
計算量: SA構築 O(N log^2 N)（Pythonの組み込みソートで実用上高速）、LCP構築 O(N)、Sparse Table前処理 O(N log N)・クエリ O(1)。全体 O(N log^2 N + Q)。"banana"の例で SA=[5,3,1,0,4,2], LCP=[_,1,3,0,0,2] を手計算し全クエリの出力が一致することを確認済み。

Step-by-Step 解説

1サフィックス配列とランク配列
ダブリング法は長さkのプレフィックス比較のランクを使い長さ2kの比較をO(1)で行う考え方をlog N回繰り返す。組み込みソートがC実装のため実用上十分高速。
2Kasaiのアルゴリズムの直感
「S[i:]の共通接頭辞長がhなら、S[i+1:]は少なくともh-1からスタートできる」という単調性を利用し、hを使い回すことで全体O(N)に抑える。
3なぜLCP区間最小値がLCEになるか
離れた接尾辞同士のLCPは、間にある隣接LCPの最小値を超えられないという単調性がある。これはサフィックス木上でLCAを辿るのと数学的に同値で、暗黙的にサフィックス木を扱っていることになる。
4Sparse TableでO(1)クエリ
LCP配列は静的なのでSparse Table（O(N log N)前処理、O(1)クエリ）が最適。長さ2^kの2区間でオーバーラップさせて覆う古典テクニック。
5正しさの検証
"banana"の手計算SA/LCPを使い、クエリ(1,3)→3, (0,2)→0, (1,1)→5がすべて一致することを確認した。

よくあるミス

ミス原因正しい書き方
LCP配列のインデックスを0-indexedのまま扱うlcp[r]=LCP(sa[r-1],sa[r])の定義を忘れるクエリ範囲を[ri+1,rj]として正しくオフセット変換する
i=jのクエリで通常のRMQ処理をするランクが等しい場合の区間が空になることを考慮していないi=jは特別扱いし答えはN-iとする
Kasaiのhを毎回0にリセットする単調性の利用（h-=1で使い回す）を知らないhを跨いで使い回さないとO(N^2)に退化する
ダブリング法でrank[i+k]の範囲外アクセス文字列末尾を超えたインデックスの処理を忘れるi+k<nでなければ-1を番兵として使う

次のステップ

  • 発展: 本問はオフラインだが、Suffix Automatonとの比較で「オンラインに文字列を追加していく場合はどうなるか」を考えてみるとよい。
  • 次回予告: ミンコフスキー和（凸多角形の辺マージによる面積計算）

自己評価

自分の回答

気づき・メモ