human
Knuth-Morris-Pratt文字列マッチングアルゴリズムの背後にあるアイデアを教えてください。
gpt
Knuth-Morris-Pratt（KMP）文字列マッチングアルゴリズムは、テキスト文字列内のパターン文字列の発生を検索するために使用される線形時間アルゴリズムです。1977年にドナルドクヌース、ヴォーンプラット、ジェームズモリスによって発明されました。

KMPアルゴリズムの背後にある主なアイデアは、既にテキスト文字列と一致しているパターン文字列に関する情報を利用することにより、不必要な比較を避けることです。具体的には、アルゴリズムは、パターンを盲目的に移動する代わりに、特定の位置での不一致の場合にパターン文字列でスキップする文字の数を伝えるテーブル（「故障関数」または「部分的な一致テーブル」と呼ばれる）をプリコンピューションします。右に1つの位置を文字列。

このテーブルを作成するために、アルゴリズムは最初に境界線アレイを構築します。これは、パターンの各位置に、その位置で終了するサブストリングエンディングの最長適切な境界の長さ（つまり、接尾辞でもある接頭辞）の長さを保存します。境界線配列は、単純なアルゴリズムを使用して線形時間に計算できます。

故障関数は、次のように境界配列から導出されます。パターン文字列の各位置について、アルゴリズムはその位置で終了するサブストリングの最も長い適切な境界の長さを計算し、境界配列の対応する値を調べます。値がゼロの場合、それは境界線がないことを意味するため、その位置の故障関数値はゼロです。それ以外の場合、アルゴリズムは現在の位置から境界の長さを差し引き、パターン文字列の次の可能な一致のインデックスを取得します。この値は、その位置の故障関数値になります。

障害関数が計算されると、アルゴリズムはそれを使用して、テキスト文字列のパターン文字列の発生を検索します。パターン文字列の最初の文字をテキスト文字列の最初の文字と比較することから始めます。それらが一致する場合、それは次のキャラクターに移動します。それらが一致しない場合、パターン文字列の現在の位置の故障関数値を調べ、比較を再開する前に多くの文字をスキップします。このプロセスは、一致が見つかるまで、またはテキスト文字列の終了に到達するまで続きます。

故障関数を使用して不必要な比較をスキップすることにより、KMPアルゴリズムは、線形時間にテキスト文字列のパターン文字列の発生を検索でき、最悪のケースの実行時間はO（M + N）です。ここで、Mは長さです。パターン文字列の長さはテキスト文字列の長さです。