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

KMPアルゴリズムの背後にある基本的なアイデアは、テキスト文字列の不必要なバックトラッキングを避けるために、既に一致しているパターン文字列に関する情報を使用することです。具体的には、アルゴリズムは部分的な一致テーブル（故障関数またはプレフィックス関数とも呼ばれる）を構築します。これは、パターンの各位置について、その位置で終了するサブストリングエンディングのプレフィックスでもある最長の適切な接尾辞の長さを示します。

このテーブルを使用すると、アルゴリズムは、既に一致している文字に基づいて、パターン文字列と一致できないテキスト文字列の特定の位置をスキップできます。パターン文字列の特定の位置でミスマッチが発生した場合、アルゴリズムは部分マッチテーブルの情報を使用して次の位置を決定して、パターンストリングの先頭までバックトラックする必要なく、パターンストリングの一致を開始します。。
human
Knuth-Morris-Prattアルゴリズムには、この「部分的なマッチング」テーブルを作成するための前処理ステップが含まれますか？また、名前は少し口いっぱいです。同じアルゴリズムの代替名がありますか？
gpt
はい、Knuth-Morris-Prattアルゴリズムは、「部分一致」表を構築する前処理ステップを含みます、
これは「失敗関数」または「部分一致テーブル」とも呼ばれます。
このテーブルはアルゴリズムのパターンマッチングの段階で使用され、不一致が発見された場合にパターン内で次に比較する位置を決定します。

前処理ステップでは、パターンを繰り返し処理し、パターンの各接頭辞について、接頭辞の接尾辞でもある接頭辞のうち最も長い接頭辞の長さを計算する。
これは、接頭辞と、その接頭辞の接尾辞となりうるすべての接尾辞を比較し、接尾辞となりうる最長の接尾辞から始めて、最短の接尾辞へと移動することで行われます。

その結果、表は整数の配列となり、各要素には対応する部分文字列の接尾辞でもあり、かつ最も長い接頭辞の長さが格納されます。
テーブルの最初の要素は常にゼロで、残りの要素はテーブルの前のエントリを使用して計算されます。

別の呼び方として、Knuth-Morris-Prattアルゴリズムは、単にKMPアルゴリズムと呼ばれることもある。
その他にも、Morris-Prattアルゴリズム（Knuthとの共著論文であるJames MorrisとVaughan Prattにちなんで命名）、Knuth-Morrisアルゴリズム、Knuthアルゴリズムなどがあります。
しかし、「Knuth-Morris-Prattアルゴリズム」というフルネームが、このアルゴリズムの最も一般的な名称である。