ローリングハッシュ（Rolling Hash）は、文字列の部分一致の高速比較や重複検出などに使われるハッシュテクニックです。特に、「部分文字列が等しいか？」というクエリを O(1) 時間で処理するのに非常に効果的です。

文字列 S の区間 S[l..r] と S[c..d] が一致するかを 高速に判定したい

• 文字列検索（Rabin-Karp法）
• 部分文字列一致判定（今回の問題）
• 重複検出（例：最長重複部分文字列）
• データの同一性検証（例：データ同期やセキュリティ）

文字列を数値に変換し、多項式として扱うことで、全体や部分の「ハッシュ値」を求めます。

'a' = 1, 'b' = 2, 'c' = 3
H("abc") = 1*31² + 2*31¹ + 3*31⁰ = 1*961 + 2*31 + 3 = 961 + 62 + 3 = 1026

→ 前のハッシュから1文字だけ足して次のハッシュが作れる （なので「ローリング（転がる）」と呼ばれる）

'a' → 1, 'b' → 2, ..., 'z' → 26

hash[i] = S[0]*BASEⁿ⁻¹ + S[1]*BASEⁿ⁻² + ... + S[i-1]*BASE⁰

→ 後で部分ハッシュ抽出に使う

prefix hash は S[0..i] のみを持っている → 任意の区間 S[l..r] を取り出したい

getHash(l, r) = (hash[r] - hash[l-1] * BASE^(r-l+1)) % MOD

S:     a  b  c  d  e
idx:   1  2  3  4  5

hash[5] = hash of "abcde"
hash[2] = hash of "a"

S[3..5] = "cde" = hash[5] - hash[2] * BASE^3

• ハッシュ値が非常に大きくなる
• オーバーフローや衝突を避ける必要がある

• 素数MOD（例：10^9 + 7）で制限し、衝突率も下げる

hash = (hash[i - 1] * BASE + value) % MOD;

• 異なる文字列が同じハッシュ値になる「衝突」がまれに発生する
• 対策：
  • MODやBASEを工夫する（大きな素数）
  • 二重ハッシュ：別のMOD・BASEで2組のハッシュを比較する

• 最長共通部分文字列を求める（バイナリサーチ + ローリングハッシュ）
• Plagiarism 検出（類似文比較）
• ファイル差分検出（rsyncアルゴリズム）