ハッシュが同じなら候補にする
Rabin–Karp法は、長さmのパターンとテキストの各長さmの窓をハッシュ値で比べます。値が違えばその窓は一致しませんが、値が同じでも内容が等しいとは限りません。実際の文字列を比較して確かめる版と、ハッシュの一致をそのまま答えにする確率的な版を区別します。ハッシュは暗号学的な秘密を守る目的ではなく、候補を素早く絞るための指紋です。一般のハッシュ表と同様、衝突の性質と入力の与えられ方が性能や保証に影響します。
123から234へ窓を進める
十進の数字列で窓123を234へ進めるなら、先頭の1が担っていた100を引き、残り23を10倍し、新しい4を足せば234です。実際には法qを取った値で同じ操作を行い、先頭の桁に対応するr^(m−1) mod qを前計算します。q=17なら123と140はどちらも余り4で、異なる内容でも衝突します。余りが同じことだけで一致を返すと誤答になります。負の剰余の扱いが言語で異なる場合には、減算後の正規化にも注意します。
期待値と最悪値を混同しない
各窓のハッシュ更新が定数時間なら、一致候補が少ない場合は前処理と走査を合わせてO(n+m)に近い処理になります。しかし検証版で多数の窓が衝突し、毎回長さmの比較が必要なら最悪O(nm)です。法や基数の選択、乱択、入力の仮定を明記せず、常に線形時間だとは言えません。検証を省けば実行時間を抑えやすくなりますが、今度は偽陽性の可能性を持ちます。正確な一致検索なのか、衝突確率を許す探索なのかが仕様の分岐点です。
同じ長さの複数パターンへ広げる
複数の同じ長さのパターンのハッシュを集合に入れておけば、本文の一つの窓から候補となるパターン群を調べられます。ただし一致したハッシュに複数のパターンが対応する場合もあるため、内容確認の費用を別に数えます。異なる長さを無制限に増やすと窓の管理も増え、一回の走査だけという説明は崩れます。空パターン、m>n、繰り返し文字、意図的に衝突する小さな法で試験すると、境界処理と検証の欠落を見つけやすくなります。