【ラビンカープほう】
ラビン・カープ法 とは？
公開:
💡 文字列の指紋を転がしながら、一致候補を探す
文字列の各区間をハッシュ値で絞り込む検索法。区間を1文字ずらしたハッシュを効率よく計算し、一致候補だけを詳しく調べる。
📌 このページのポイント
ひよこ 文章をハッシュで探せるの？
ひよこ 毎回ハッシュを作るのは大変そう。
ペンギン先生 そこでローリングハッシュを使うよ。窓を1文字ずらすとき、出ていく文字の寄与を引き、残った部分をずらし、入ってくる文字を足す。毎回、窓の全体を最初から読み直して計算しなくてよいんだ。
ひよこ 小さな数で例を見せて！
ペンギン先生 Aを1、Bを2、Cを3とし、2文字xyの値を「10×x＋yを13で割った余り」としよう。ABは12、BCは10、CAは5になる。本文ABCAでBCを探すなら、窓の値12→10→5のうち、10の位置で文字を確認するんだ。図は仕組みを見せるための小さな数だよ。
ひよこ 同じハッシュなら、確認を省いてもいい？
もっと詳しく知りたい人へ
検索は必ずO(n＋m)ですか？
本文長n、パターン長mとすると、固定幅のハッシュ計算を定数時間とみなす条件でハッシュの走査自体はO(n＋m)です。候補の文字照合を行う方式では、衝突や一致候補が多いと照合のコストが増え、単純な実装の最悪時間はO(nm)になり得ます。
まとめ：ざっくりこれだけ覚えればOK！
「ラビン・カープ法」って出てきたら「更新しやすいハッシュで、文字列の一致候補を絞る検索」と思えればだいたいOK！