文字列検索アルゴリズムの一つです。検索パターンと検索対象の部分文字列の「ハッシュ値」を比較することで、文字列の不一致を高速に判定します。
ローリングハッシュ (Rolling Hash)
検索窓を1文字ずらす際、全ての文字のハッシュを再計算するのではなく、「抜ける文字」と「入る文字」の差分だけを計算してハッシュ値を更新します。これにより、ハッシュの再計算が O(M) ではなく O(1) で行えます。
擬陽性 (Spurious Hit)
異なる文字列でもハッシュ値が偶然一致してしまうこと（ハッシュ衝突）。そのため、ハッシュが一致した場合は念のため実際の文字列比較を行う必要があります。
共有コメント 共有されるコメント欄です。