Day 036-Q5 | ローリングハッシュ二分探索 — 最長共通部分文字列マルチクエリ

問題

$N$ 個の文字列 $S_1, \ldots, S_N$ が与えられる。$Q$ 個のクエリ $(i, j)$ に対して， $S_i$ と $S_j$ の 最長共通部分文字列（LCS: Longest Common Substring） の長さを答えよ。

制約

$1 \le N \le 100$

$1 \le |S_k| \le 2000$

$L = \sum|S_k| \le 2 \times 10^5$

$1 \le Q \le 5000$

英小文字のみ

時間制限: 2sec

入出力例

入力例 1

3
abcde
bcdef
xbcdy
2
1 2
1 3

出力例 1

4
3

$S_1 \cap S_2$: bcde が最長共通部分文字列（長さ4）
$S_1 \cap S_3$: bcd が最長共通部分文字列（長さ3）

概念図: 二分探索 + ローリングハッシュ

ヒント (段階的開示)

ヒント1: 方向性

「長さ $l$ の共通部分文字列が存在するか」を判定し，$l$ を二分探索で求める。存在判定は 2重ローリングハッシュで $O(|S_i| + |S_j|)$。

ヒント2: ローリングハッシュの構築

$h[i+1] = h[i] \cdot B + \text{ord}(s[i])$，$p[i+1] = p[i] \cdot B$（共に $\mod M$）。
部分文字列 $s[l..r]$ のハッシュ: $(h[r+1] - h[l] \cdot p[r-l+1]) \mod M$。

ヒント3: 2重ハッシュで衝突回避

$(\text{hash}_1, \text{hash}_2)$ のペアを set に入れることで，衝突確率を $\approx 10^{-18}$ に抑える。

hset = set()
for k in range(ni - l + 1):
    hset.add((get_h1(k, k+l-1), get_h2(k, k+l-1)))
for k in range(nj - l + 1):
    if (get_h1(k,k+l-1), get_h2(k,k+l-1)) in hset:
        return True

模範解答 (Python)

import sys
input = sys.stdin.readline

MOD1, BASE1 = (1 << 61) - 1, 131
MOD2, BASE2 = 10**9 + 7, 137

def build(s):
    n = len(s)
    pw1 = [1] * (n + 1)
    pw2 = [1] * (n + 1)
    h1 = [0] * (n + 1)
    h2 = [0] * (n + 1)
    for i, c in enumerate(s):
        h1[i+1] = (h1[i] * BASE1 + ord(c)) % MOD1
        h2[i+1] = (h2[i] * BASE2 + ord(c)) % MOD2
        pw1[i+1] = pw1[i] * BASE1 % MOD1
        pw2[i+1] = pw2[i] * BASE2 % MOD2
    return n, h1, h2, pw1, pw2

def get_h(h1, h2, pw1, pw2, l, r):
    v1 = (h1[r+1] - h1[l] * pw1[r-l+1]) % MOD1
    v2 = (h2[r+1] - h2[l] * pw2[r-l+1]) % MOD2
    return (v1, v2)

def lcs_len(data_i, data_j):
    ni, h1i, h2i, pw1i, pw2i = data_i
    nj, h1j, h2j, pw1j, pw2j = data_j

    def check(l):
        if l == 0:
            return True
        hset = set()
        for k in range(ni - l + 1):
            hset.add(get_h(h1i, h2i, pw1i, pw2i, k, k+l-1))
        for k in range(nj - l + 1):
            if get_h(h1j, h2j, pw1j, pw2j, k, k+l-1) in hset:
                return True
        return False

    lo, hi = 0, min(ni, nj)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if check(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

def solve():
    N = int(input())
    strings = [input().strip() for _ in range(N)]
    data = [build(s) for s in strings]

    Q = int(input())
    out = []
    for _ in range(Q):
        i, j = map(int, input().split())
        i -= 1; j -= 1
        out.append(str(lcs_len(data[i], data[j])))
    print('\n'.join(out))

solve()

Step-by-Step 解説

1ローリングハッシュの構築
各文字列について前処理で prefix hash と累乗テーブルを作成。$O(|S|)$ で構築。部分文字列ハッシュは $O(1)$ で取得。

2check(l) の実装
$S_i$ の全長さ $l$ 部分文字列の 2重ハッシュ値を set に追加（$O(|S_i|)$）。 $S_j$ の各長さ $l$ 部分文字列がその set に含まれるか確認（$O(|S_j|)$）。

3二分探索
「長さ $l$ の共通部分文字列が存在する」は $l$ に対して単調なので二分探索が使える。 $O(\log \min(|S_i|, |S_j|))$ 回の check 呼び出し。

4衝突回避
2重ハッシュ（MOD1, BASE1 と MOD2, BASE2 の2対）により衝突確率を $\approx 10^{-18}$ に抑える。

計算量

前処理: $O(L)$（全文字列合計長）
1 クエリ: $O((|S_i|+|S_j|) \log \min(|S_i|,|S_j|))$
全体: $O(L + Q \cdot L_{\max} \cdot \log L_{\max})$

よくあるミス

ミス	原因	正しい書き方
pw テーブルのサイズ不足	`pw[n]` まで必要	`[1]*(n+1)` で n+1 要素
`check(0)` での境界	長さ0への対応	`if l==0: return True`
1重ハッシュのみ	衝突で WA	2重ハッシュを使う
二分探索の方向	lo/hi の更新	`mid=(lo+hi+1)//2` で上側二分探索

次のステップ

発展: $N$ 文字列の全ペア最長共通部分文字列を $O(L^2 / 64)$ bitset で高速化
応用: Suffix Automaton を使った $O(L)$ LCS 計算

自己評価

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

Day 036-Q5 — ローリングハッシュ二分探索 — 最長共通部分文字列マルチクエリ

問題

制約