Day 022-Q1 | サフィックス配列（SA-IS + LCP配列）

問題

長さ $N$ の文字列 $S$ が与えられる。以下のクエリに $Q$ 回答えよ。

クエリ L R: $S$ の全サフィックスのうち、辞書順で $L$ 番目から $R$ 番目（1-indexed）のサフィックスが共通して持つ最長プレフィックスの長さを答えよ。

すなわち、サフィックス配列 $SA$ に基づき、$SA[L-1], SA[L], \ldots, SA[R-1]$ が始点となるサフィックスの LCP（Longest Common Prefix）の長さを求めよ。

入力形式

N Q
S
L_1 R_1
L_2 R_2
...
L_Q R_Q

制約

$1 \leq N \leq 2 \times 10^5$

$1 \leq Q \leq 2 \times 10^5$

$S$ は英小文字のみからなる

$1 \leq L_i \leq R_i \leq N$

入出力例

入力例 1

7 3
abcabcd
1 3
2 5
4 4

出力例 1

2
1
3

abcabcd のサフィックス配列は辞書順に並べると: abcabcd(0), abcd(3), bcabcd(1), bcd(4), cabcd(2), cd(5), d(6) → SA = [0,3,1,4,2,5,6]

ヒント (段階的開示)

ヒント1: 方向性

サフィックス配列 SA と LCP 配列を構築し、区間 $[L, R]$ の LCP は LCP 配列上の区間最小値（RMQ）で求められる。

ヒント2: アプローチ

(1) SA-IS 法（または DC3 法）で $O(N)$ にサフィックス配列を構築、(2) Kasai のアルゴリズムで $O(N)$ に LCP 配列を構築、(3) Sparse Table で $O(N \log N)$ の前処理 → $O(1)$ の区間最小値クエリ、(4) クエリ L R は min(LCP[L], LCP[L+1], ..., LCP[R-1])。

ヒント3: 誘導

import sys
from math import log2

def build_sparse_table(arr):
    n = len(arr)
    k = max(1, int(log2(n)) + 1) if n > 0 else 1
    LOG = [0] * (n + 1)
    for i in range(2, n + 1):
        LOG[i] = LOG[i // 2] + 1
    sparse = [arr[:]]
    for j in range(1, k + 1):
        prev = sparse[j-1]
        cur = []
        for i in range(n - (1 << j) + 1):
            cur.append(min(prev[i], prev[i + (1 << (j-1))]))
        sparse.append(cur)
        if not cur:
            break
    return sparse, LOG

def rmq(sparse, LOG, l, r):
    if l > r:
        return float('inf')
    length = r - l + 1
    k = LOG[length]
    return min(sparse[k][l], sparse[k][r - (1 << k) + 1])

模範解答 (Python)

import sys
from math import log2
input = sys.stdin.readline

def build_suffix_array(s):
    """SA-IS O(N) suffix array construction (simplified O(N log N) version)"""
    n = len(s)
    if n == 1:
        return [0]
    sa = sorted(range(n), key=lambda i: s[i:])
    return sa

def kasai(s, sa):
    """LCP array construction in O(N)"""
    n = len(s)
    rank = [0] * n
    for i, v in enumerate(sa):
        rank[v] = i
    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
    return lcp

def build_sparse_table(arr):
    n = len(arr)
    if n == 0:
        return [[]], [0]
    LOG = [0] * (n + 1)
    for i in range(2, n + 1):
        LOG[i] = LOG[i // 2] + 1
    k = LOG[n] + 1
    sparse = [arr[:]]
    j = 1
    while (1 << j) <= n:
        prev = sparse[j-1]
        length = n - (1 << j) + 1
        if length <= 0:
            break
        cur = [min(prev[i], prev[i + (1 << (j-1))]) for i in range(length)]
        sparse.append(cur)
        j += 1
    return sparse, LOG

def rmq(sparse, LOG, l, r):
    if l > r:
        return float('inf')
    length = r - l + 1
    k = LOG[length]
    return min(sparse[k][l], sparse[k][r - (1 << k) + 1])

def main():
    N, Q = map(int, input().split())
    S = input().strip()

    sa = build_suffix_array(S)
    lcp = kasai(S, sa)

    sparse, LOG = build_sparse_table(lcp)

    results = []
    for _ in range(Q):
        L, R = map(int, input().split())
        if L == R:
            results.append(N - sa[L-1])
        else:
            ans = rmq(sparse, LOG, L, R - 1)
            results.append(ans)

    print('\n'.join(map(str, results)))

main()

Step-by-Step 解説

1サフィックス配列（SA）の構築
サフィックス配列とは、文字列 $S$ の全サフィックスを辞書順にソートした際の開始インデックスの配列。本解答では簡易版 sorted(range(n), key=lambda i: s[i:]) を使用（$O(N^2 \log N)$）。本番では SA-IS アルゴリズム（$O(N)$）を使う。

2LCP 配列の構築（Kasai 法）
rank[i]: サフィックス i がSAの何番目か。Kasai の要点: rank[i] のサフィックスと rank[i]-1 番目のサフィックスの LCP は前のステップの LCP - 1 以上（h の値を再利用してO(N)を達成）。

3Sparse Table による RMQ
LCP 配列上で区間最小値を $O(1)$ で求める。前処理 $O(N \log N)$、クエリ $O(1)$。

4クエリ処理
SA 上の区間 $[L, R]$ の LCP = min(lcp[L], lcp[L+1], ..., lcp[R-1])。インデックスは 0-based で lcp[L..R-1]、1-based クエリを変換する。

よくあるミス

ミス	原因	正しい書き方
`lcp[L-1..R-1]` のインデックスがずれる	LCP 配列は隣接間なのでオフセットに注意	`lcp[L..R-1]`（0-based, SA インデックス）
$L = R$ の特殊ケースを忘れる	単一サフィックスのLCPは自分自身の長さ	`N - sa[L-1]` を返す
SA-IS の実装バグ	符号付き整数のオーバーフローや境界条件	まず `sorted` で正しさを確認してから最適化
Kasai で `h` を引き忘れる	毎イテレーションで `h -= 1` が必要	`if h > 0: h -= 1`

次のステップ

発展問題: 異なる文字列間の最長共通部分列を SA + LCP で求める（複数文字列の結合 + 番兵文字）
さらに難しい: Suffix Automaton で部分文字列の出現回数を $O(N)$ で計算

自己評価

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

Day 022-Q1 — 文字列のサフィックス配列（SA-IS + LCP配列）

問題