Day 039-Q3 | 二次元ローリングハッシュ（2D Rolling Hash）

問題

$H \times W$ のグリッド（英小文字）と $P \times Q$ のパターン（英小文字）が与えられる。グリッド中にパターンが何回出現するか（重複あり）を求めよ。

制約

$1 \le P \le H \le 1000$

$1 \le Q \le W \le 1000$

$S, T$ は英小文字のみ

時間制限: 2sec / メモリ: 256MB

入出力例

入力例 1

4 5 2 3
abcab
bcdea
abcde
bcdea
abc
bcd

出力例 1

パターン = ["abc","bcd"]。グリッドの (0,0) と (1,0) から始まる 2×3 矩形と (2,0) から始まる矩形を確認。

概念図: 2 段階ハッシュ

ヒント（段階的開示）

ヒント1: 方向性

2D パターンマッチングは「縦方向ハッシュ → 横方向ハッシュ」の 2 段階で実現。まず各列の縦 $P$ 文字ハッシュを計算し、次に横方向にスライドウィンドウを走らせる。

ヒント2: prefix hash の使い方

縦方向 prefix hash: ph_col[i+1][j] = ph_col[i][j] * BASE_R + val[i][j]
縦 $P$ 文字ハッシュ: ph_col[i+P][j] - ph_col[i][j] * pow_r[P]

ヒント3: ローリングウィンドウ

# 横方向ローリングハッシュ（長さ Q）
cur = 0
for j in range(Q):
    cur = (cur * BASE_C + col_hashes[j]) % MOD
if cur == pat_hash: count += 1

for j in range(Q, W):
    cur = (cur * BASE_C + col_hashes[j]) % MOD
    cur = (cur - col_hashes[j-Q] * pow_c[Q]) % MOD
    if cur == pat_hash: count += 1

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    H, W, P, Q = map(int, input().split())
    grid = [input().strip() for _ in range(H)]
    pattern = [input().strip() for _ in range(P)]

    MOD = (1 << 61) - 1
    BASE_R = 131
    BASE_C = 137

    def madd(a, b): return (a + b) % MOD
    def mmul(a, b): return a * b % MOD

    pow_r = [1] * (H + 1)
    for i in range(1, H + 1):
        pow_r[i] = mmul(pow_r[i-1], BASE_R)
    pow_c = [1] * (W + 1)
    for j in range(1, W + 1):
        pow_c[j] = mmul(pow_c[j-1], BASE_C)

    val = [[ord(grid[i][j]) - ord('a') + 1 for j in range(W)] for i in range(H)]

    ph_col = [[0] * W for _ in range(H + 1)]
    for i in range(H):
        for j in range(W):
            ph_col[i+1][j] = madd(mmul(ph_col[i][j], BASE_R), val[i][j])

    # パターンのハッシュ
    pat_val = [[ord(pattern[r][c]) - ord('a') + 1 for c in range(Q)] for r in range(P)]
    ph_pat = [[0] * Q for _ in range(P + 1)]
    for r in range(P):
        for c in range(Q):
            ph_pat[r+1][c] = madd(mmul(ph_pat[r][c], BASE_R), pat_val[r][c])

    pat_col_h = [ph_pat[P][c] for c in range(Q)]
    pat_hash = 0
    for c in range(Q):
        pat_hash = madd(mmul(pat_hash, BASE_C), pat_col_h[c])

    count = 0
    for i in range(H - P + 1):
        col_hashes = []
        for j in range(W):
            h = (ph_col[i+P][j] - mmul(ph_col[i][j], pow_r[P])) % MOD
            col_hashes.append(h)

        cur = 0
        for j in range(Q):
            cur = madd(mmul(cur, BASE_C), col_hashes[j])
        if cur == pat_hash:
            count += 1

        for j in range(Q, W):
            cur = madd(mmul(cur, BASE_C), col_hashes[j])
            cur = (cur - mmul(col_hashes[j - Q], pow_c[Q])) % MOD
            if cur == pat_hash:
                count += 1

    print(count)

solve()

Step-by-Step 解説

1縦方向 Prefix Hash の構築
各列 $j$ について ph_col[i+1][j] = ph_col[i][j] * BASE_R + val[i][j]。縦 $P$ 文字ハッシュは引き算で $O(1)$ に抽出可能。

2パターンの縦ハッシュ列
パターンも同様に縦方向 prefix hash を計算し、$P$ 行分をまとめた列ハッシュを得る。

3パターンのハッシュ値
縦ハッシュ列 $Q$ 個を横方向に BASE_C 進数でまとめて 1 つのハッシュ値とする。

4横方向ローリングハッシュ
各開始行 $i$ で、列ハッシュ配列を横にスライドウィンドウ（長さ $Q$）で走査。追加・削除 $O(1)$。

5ハッシュ衝突対策
Mersenne 素数 $2^{61}-1$ を MOD に使うことで衝突確率を低減。本番ではダブルハッシュを検討。

計算量

前処理（縦ハッシュ）: $O(HW)$
各行のローリングハッシュ: $O(W)$ × $(H-P+1)$ 行 = $O(HW)$
合計: $O(HW)$

よくあるミス

ミス	原因	正しい書き方
縦横の BASE が同じ	ハッシュ空間が重なり衝突増加	`BASE_R=131, BASE_C=137` と別々に設定
mod 演算で負の値	引き算後に負になる	`% MOD` を忘れずに（Python は非負だが確認）
pow_c の次数ミス	削除時の冪を誤る	$Q$ 文字窓なら最古の要素寄与は `pow_c[Q]`
文字マッピングで 0 を使う	空文字と区別できない	`ord(c) - ord('a') + 1` で 1 始まりにする

次のステップ

発展: 複数パターン → Aho-Corasick + 2D ハッシュ
応用: 最大正方形マッチング → 二分探索 + 2D ローリングハッシュ

自己評価

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

Day 039-Q3 — 二次元ローリングハッシュ（2D Rolling Hash）

問題

制約