0Pricing
Competitive Programming Academy · レッスン

パターン検索の Z 関数

文字列全体で接頭辞を照合します

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

もう一つのマッチング手法

Z関数は、パターン検索で使えるKMPのすっきりした代替手法です。こちらのほうが考え方を理解しやすいと感じる人も多くいます。✨

z[i]の意味

各インデックスについて、z[i]は、iから始まり、文字列全体のプレフィックスとも一致する最長の部分文字列の長さです。

小さな例

aabaab の z は 0,1,0,3,1,0 です。インデックス3ではaabがプレフィックスと一致するため、長さは3になります。

Zボックス

これまでに見つかった最も右側の一致範囲である[l, r]を管理します。これにより、以前の比較結果を再利用できます。

l, r = 0, 0

ボックスの内側

iがボックスの内側にある場合は、既知のzの値をコピーして初期値にします。ただし、ボックスの右端が上限です。

if i < r:
    z[i] = min(r - i, z[i - l])

ボックスを越えて拡張

初期値を設定した後は、プレフィックスと一致する限り、文字を1つずつ比較し続けます。

while i + z[i] < n and s[z[i]] == s[i + z[i]]:
    z[i] += 1

ボックスを右へ移動

一致範囲がさらに右まで到達した場合は、将来のインデックスで再利用できるようにlとrを更新します。

if i + z[i] > r:
    l, r = i, i + z[i]

線形時間の保証

ボックスは右方向にしか移動しないため、全体の計算量はO(n)です。各文字が費やす計算量には上限があります。

Z関数で検索

pattern + sep + textを連結してZ関数を計算します。パターンの長さと等しいzの値が見つかれば、それが一致箇所です。

combined = pattern + chr(0) + text
z = z_function(combined)

一致箇所の読み取り

Z配列を走査し、z[i] == len(pattern)となる場所では、対応するテキスト上の位置から一致が始まります。

if z[i] == len(pattern):
    matches.append(i - len(pattern) - 1)

Z関数とKMP

Z関数とKMPはどちらも線形時間で動作します。Z関数はコードがより単純なことが多いため、手元に用意しておくと便利な代替手法です。

確認

Z配列の意味をしっかり理解できているか確認してください。

まとめ：Z関数の力

スライドするボックスを使ってZ配列を構築し、線形時間で検索できるようになりました。これでKMPのすっきりした代替手法も手に入りました。🎯

よくある質問

「パターン検索の Z 関数」レッスンは無料ですか？

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

「パターン検索の Z 関数」で何を学びますか？

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

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

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

「パターン検索の Z 関数」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

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