Rabin指紋
ローリングハッシュで部分文字列を高速検索するパズル
Rabin-Karp 法はパターン長 m と本文長 n に対し平均 O(n+m) でマッチを発見する。
本文上で長さ m の窓のハッシュを
h_{i+1} = (h_i − s[i]·B^{m−1})·B + s[i+m] と転がしながら更新するため、毎回全文走査せずに済む。
本ゲームでは更新を1ステップずつ可視化、可逆ロールバック (←) で巻き戻せる。横山研の rabin-karp プロジェクト由来。
Stage
1/4
Pos
0
Window Hash
—
Pattern Hash
—
Found
0
Coll.
0
パターン
本文
操作履歴 (可逆)
発見位置
緑=ハッシュ一致＋文字列一致 (true positive)、赤=ハッシュ一致だが文字列不一致 (collision)。Rabin-Karp は最終確認に文字比較が必要。
操作
「1ステップ進む」で窓を1つ右に転がす。窓ハッシュとパターンハッシュが一致したら、文字列を比較して真の一致か衝突かを判定。
「ロールバック」で巻き戻し。Rabin-Karpの可逆な更新式を体感。
勝利条件: 全パターンを O(n+m) 計算量内 (=1パスで) に発見すること。