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

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

このテーブルを使用すると、アルゴリズムは、既に一致している文字に基づいて、パターン文字列と一致できないテキスト文字列の特定の位置をスキップできます。パターン文字列の特定の位置でミスマッチが発生した場合、アルゴリズムは部分マッチテーブルの情報を使用して次の位置を決定して、パターンストリングの先頭までバックトラックする必要なく、パターンストリングの一致を開始します。。
human
Knuth-Morris-Prattアルゴリズムには、この「部分的なマッチング」テーブルを作成するための前処理ステップが含まれますか？また、名前は少し口いっぱいです。同じアルゴリズムの代替名がありますか？
gpt
そう、Knuth-Morris-Pratt (KMP)アルゴリズムには、部分一致表を計算する前処理ステップがあります。部分一致表は、パターンの各接頭辞のうち、最も長い接尾辞の長さを格納する配列です。

KMPアルゴリズムは、James H. MorrisとVaughan Prattが独自に発見し、後にDonald Knuthが簡略化して発表したことから、Knuth-Morris-Pratt-Powellアルゴリズムと呼ばれることもある。また、モリスとプラットの名前をとって「MP」アルゴリズムと呼ばれることもある。