Day 066-Q1 | Suffix Array + LCE クエリ高速化

問題

長さ $N$ の文字列 $S$ と $Q$ 個のクエリが与えられる。各クエリは $(l_1, l_2)$ の形で、$S[l_1..]$ と $S[l_2..]$ の最長共通拡張（LCE: Longest Common Extension）の長さを求めよ。

制約

パラメータ	範囲
$N$	$1 \le N \le 2 \times 10^5$
$Q$	$1 \le Q \le 2 \times 10^5$
$l_1, l_2$	$0 \le l_1, l_2 < N$

入出力例

入力例 1

13 4
abracadabra$z
0 7
1 8
0 3
2 9

出力例 1

LCE(0,7)=4: "abra" が共通。LCE(1,8)=3: "bra" が共通。

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

ヒント（段階的開示）

ヒント1: 方向性

LCE(l1, l2) は「Suffix Array + LCP Array + Sparse Table による RMQ」で O(N log N) 前処理・O(1) クエリ実現できる。SA 上で l1 と l2 の順位 r1, r2 を求め、LCP[min(r1,r2)+1 .. max(r1,r2)] の最小値が LCE に等しい。

ヒント2: アプローチ

SA-IS 法（または O(N log N) のダブリング法）で Suffix Array を構築
Kasai 法で LCP Array を O(N) で構築
Sparse Table で LCP Array の RMQ を O(N log N) 前処理・O(1) クエリ
LCE(l1, l2): rank[l1]=r1, rank[l2]=r2 として RMQ(min(r1,r2)+1, max(r1,r2)) を返す

ヒント3: コード骨格

# SA 上の位置を rank 配列で引く
rank = [0] * N
for i, s in enumerate(sa):
    rank[s] = i

def lce(l1, l2):
    if l1 == l2: return N - l1
    r1, r2 = rank[l1], rank[l2]
    if r1 > r2: r1, r2 = r2, r1
    return rmq(r1 + 1, r2)  # LCP[r1+1..r2] の最小値

模範解答 (Python)

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

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

def build_lcp(s, sa):
    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(lcp):
    n = len(lcp)
    LOG = max(1, int(log2(n)) + 1) if n > 1 else 1
    sp = [lcp[:]]
    for k in range(1, LOG + 1):
        prev = sp[-1]
        cur = [min(prev[i], prev[i + (1 << (k-1))]) if i + (1 << k) <= n else prev[i] for i in range(n)]
        sp.append(cur)
    return sp

def rmq(sp, l, r):
    if l > r: return 0
    k = int(log2(r - l + 1))
    return min(sp[k][l], sp[k][r - (1 << k) + 1])

def solve():
    N, Q = map(int, input().split())
    S = input().strip()
    sa = build_sa(S)
    lcp = build_lcp(S, sa)
    sp = build_sparse(lcp)
    rank = [0] * N
    for i, v in enumerate(sa):
        rank[v] = i

    out = []
    for _ in range(Q):
        l1, l2 = map(int, input().split())
        if l1 == l2:
            out.append(N - l1)
            continue
        r1, r2 = rank[l1], rank[l2]
        if r1 > r2:
            r1, r2 = r2, r1
        out.append(rmq(sp, r1 + 1, r2))
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

Step 1: Suffix Array と LCP Array

SA は全サフィックスを辞書順にソートした配列。LCP[i] は sa[i-1] と sa[i] の共通プレフィックス長。Kasai 法で O(N) 構築できる（各サフィックスを一度ずつ処理する不変量を利用）。

Step 2: Sparse Table による RMQ

LCP 配列上の区間最小を O(1) で答える。前処理は O(N log N)。$sp[k][i] = lcp[i..i+2^k-1]$ の最小値として、任意区間 $[l,r]$ は $k = \lfloor \log_2(r-l+1) \rfloor$ として $\min(sp[k][l], sp[k][r-2^k+1])$ で求まる。

Step 3: LCE の導出原理

SA の隣接するサフィックス間の LCP は LCP Array で定義される。任意 2 サフィックスの LCE は、SA 上でその間にある全サフィックスとの LCP の最小値に等しい（三角不等式的な性質）。

Step 4: 計算量まとめ

処理	計算量
SA 構築（ダブリング）	$O(N \log N)$
LCP 構築（Kasai）	$O(N)$
Sparse Table 前処理	$O(N \log N)$
クエリ 1 回	$O(1)$
全体	$O((N + Q) \log N)$

よくあるミス

ミス	原因	正しい書き方
rank と sa の混同	sa[i]=j は「i番目のサフィックスが j から始まる」	rank[j]=i（逆引き）で使う
RMQ 区間の端点設定ミス	LCP[r1] でなく LCP[r1+1] から	`rmq(r1+1, r2)`
l1==l2 の特殊ケース漏れ	rank が同じになり RMQ が意味をなさない	先に `return N - l1`

次のステップ

発展問題: LCE クエリを使い、文字列 S から重複する部分文字列の最長長を O(N log N) で求めよ（LCP Array の最大値だが、任意ペアの最長共通部分文字列への拡張も含めて考察せよ）。

自己評価

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