0Pricing
Competitive Programming Academy · レッスン

多項式文字列ハッシュ

部分文字列を定数時間で比較します

「多項式文字列ハッシュ」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

部分文字列を高速に比較する

2つの部分文字列が等しいかを調べる場面はよくあります。文字を1つずつ比較する方法は遅いため、各文字列を数値に変換します。🔢

ハッシュの考え方

ハッシュは、文字列を1つの整数に対応付けます。2つの文字列が異なれば、それらのハッシュもほとんどの場合異なります。

文字列を多項式として扱う

各文字を p 進数の1桁として読み取ります。この多項式としての見方により、文字列を1つの重み付き和に変換できます。

h = ord(s[0]) + ord(s[1]) * p + ord(s[2]) * p * p

基数と法を選ぶ

31のような素数の基数と、大きな素数の法を選びます。法を取ることで数値を小さく保ち、オーバーフローを防ぎます。

BASE = 31
MOD = 10**9 + 9

1つのハッシュを計算する

文字列を順にたどり、各文字をHornerの方法で取り込みながら、各ステップで法を取ります。

h = 0
for c in s:
    h = (h * BASE + ord(c)) % MOD

prefix hash

各位置についてprefix hashを保存します。すると、任意の部分文字列のハッシュを素早い引き算で求められます。

pre[i + 1] = (pre[i] * BASE + ord(s[i])) % MOD

基数のべき乗

基数のべき乗もあらかじめ計算しておきます。引き算を行うときに、2つの接頭辞の位置をそろえるために使います。

pw[i] = (pw[i - 1] * BASE) % MOD

O(1)で部分文字列のハッシュを求める

s[l..r] のハッシュは、2つの prefix hash の引き算にべき乗を掛けて求められます。クエリ1回あたり定数時間です。

def sub(l, r):
    return (pre[r] - pre[l] * pw[r - l]) % MOD

衝突に注意

異なる2つの文字列が同じハッシュ値を持つことがあり、これを衝突と呼びます。まれなことですが、コンテストでは衝突を引き起こす入力が意図的に作られる場合があります。

安全のための二重ハッシュ

独立した2つの法を使い、両方のハッシュを比較します。両方で同時に衝突することは、実質的にありえません。

ハッシュが活躍する場面

ハッシュは部分文字列の比較、繰り返しの検出、パターン検索に利用できます。柔軟に使える万能ツールです。

確認

多数の部分文字列を安全に比較するには、適切なツールを選んでください。

まとめ：ハッシュの力

これで文字列を多項式ハッシュに変換し、任意の部分文字列を O(1) で取得し、衝突にも対策できるようになりました。🚀

よくある質問

「多項式文字列ハッシュ」レッスンは無料ですか？

はい。「多項式文字列ハッシュ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「多項式文字列ハッシュ」で何を学びますか？

部分文字列を定数時間で比較します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「多項式文字列ハッシュ」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. KMP の接頭辞関数
  2. 多項式文字列ハッシュ
  3. パターン検索の Z 関数
  4. 接頭辞検索のための Trie
← Competitive Programming Academyに戻る