0Pricing
Competitive Programming Academy · レッスン

KMP の接頭辞関数

O(n + m) でパターンを見つけます

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

パターンマッチング問題

大きなテキストの中で小さなパターンが現れる位置を見つけたいとします。単純な照合は遅いため、競技プログラミングではより賢い探索が求められます。🔍

単純検索が遅い理由

すべての位置でパターンを比較すると、計算量はO(n*m)になることがあります。入力が大きいと、気付かないうちに制限時間を超えてしまいます。

prefix functionを使う

prefix functionは、各位置で、同時に接尾辞でもある最長の真の接頭辞の長さを表します。これはKMPの中心となる仕組みです。

真の接頭辞と接尾辞

真の接頭辞や接尾辞では、文字列全体そのものは除外します。ababa では、最長の一致する組の長さは3で、aba です。

pi[i]に保存するもの

値は pi という配列に保存します。ここで pi[i] は、インデックス i で終わる部分文字列における、最長の接頭辞と接尾辞の一致長です。

piを1回の走査で構築する

piは左から右へ構築し、最初から再比較する代わりに以前の値を再利用します。この再利用こそが仕組みの要点です。

def prefix_function(s):
    pi = [0] * len(s)
    return pi

フォールバックのループ

文字が一致しないときは、0に戻す代わりにpi[k-1]へフォールバックします。これにより、同じ処理をやり直さずに済みます。

while k > 0 and s[i] != s[k]:
    k = pi[k - 1]

一致を延長する

現在の文字が一致したら、長さを1増やして記録します。長さ0の状態で不一致になった場合は、そのまま0です。

if s[i] == s[k]:
    k += 1
pi[i] = k

この仕組みで検索する

テキストからパターンを検索するには、pattern + sep + textの形で連結します。パターンの長さと等しい pi の値が、完全一致の位置を示します。

combined = pattern + chr(0) + text
pi = prefix_function(combined)

区切り文字が重要な理由

区切り文字には、どちらの文字列にも含まれない記号を使います。これにより、連結部分をまたいで一致したように見える誤検出を防げます。

線形時間のメリット

構築と検索はどちらもO(n + m)で実行できます。各文字を1回処理するだけなので、KMPは非常に大きな競技プログラミングの入力にも対応できます。

理解度チェック

prefix function が何を記録するのか、理解度を確認しましょう。

まとめ: KMPの要点

prefix functionについて学びました。pi を一度構築し、不一致時にフォールバックすることで、線形時間で検索できます。これがKMPの要点です。🎯

よくある質問

「KMP の接頭辞関数」レッスンは無料ですか？

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

「KMP の接頭辞関数」で何を学びますか？

O(n + m) でパターンを見つけます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「KMP の接頭辞関数」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

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