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

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

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

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

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

故障関数を使用して不必要な比較をスキップすることにより、KMPアルゴリズムは、線形時間にテキスト文字列のパターン文字列の発生を検索でき、最悪のケースの実行時間はO（M + N）です。ここで、Mは長さです。パターン文字列の長さはテキスト文字列の長さです。
The Knuth-Morris-Pratt (KMP) string matching algorithm is a linear-time algorithm used to search for occurrences of a pattern string in a text string. It was invented by Donald Knuth, Vaughan Pratt, and James Morris in 1977.

The main idea behind the KMP algorithm is to avoid unnecessary comparisons by taking advantage of information about the pattern string that has already been matched with the text string. Specifically, the algorithm precomputes a table (known as the "failure function" or "partial match table") that tells it how many characters to skip in the pattern string in case of a mismatch at a particular position, instead of blindly moving the pattern string one position to the right.

To create this table, the algorithm first constructs a border array, which stores for each position in the pattern string the length of the longest proper border (i.e., a prefix that is also a suffix) of the substring ending at that position. The border array can be computed in linear time using a simple algorithm.

The failure function is then derived from the border array as follows. For each position in the pattern string, the algorithm computes the length of the longest proper border of the substring ending at that position, and then looks up the corresponding value in the border array. If the value is zero, it means that there is no border, so the failure function value for that position is zero. Otherwise, the algorithm subtracts the length of the border from the current position and gets the index of the next possible match in the pattern string. This value becomes the failure function value for that position.

Once the failure function has been computed, the algorithm uses it to search for occurrences of the pattern string in the text string. It starts by comparing the first character of the pattern string with the first character of the text string. If they match, it moves on to the next character. If they do not match, it looks up the failure function value for the current position in the pattern string and skips that many characters before resuming the comparison. This process continues until a match is found or the end of the text string is reached.

By using the failure function to skip over unnecessary comparisons, the KMP algorithm can search for occurrences of a pattern string in a text string in linear time, with a worst-case running time of O(m + n), where m is the length of the pattern string and n is the length of the text string.