Knuth-Morris-Pratt（KMP）アルゴリズムは、文字列検索アルゴリズムです。「テキスト」の「単語」wの発生を見つける問題を解決します。
重要なアイデアは、キャラクターのマッチングから得られる情報を使用してテキストのセクションをスキップし、素朴なアプローチよりも効率的にすることです。
これを行います：

wという単語に基づいて「部分的なマッチテーブル」を構築する
ミスマッチが発生するたびに、テーブルを使用して、テキストをスキップする距離を決定します（1文字をスキップするだけではありません）

これにより、ミスマッチから迅速に「回復」し、テキストの大きなセクションをスキップすることが多く、非常に効率的になります。
最終結果は、線形時間の複雑さ（入力文字列の長さに比例）を備えたアルゴリズムです。

要するに、重要な洞察は、単語から情報を事前に計算し、それを使用してテキストのセクションから効率的に「回復」し、素朴なアプローチよりも速くすることです。
The Knuth-Morris-Pratt (KMP) algorithm is a string searching algorithm. It solves the problem of finding occurrences of a "word" W within a "text" S.
The key idea is that it uses the information it gains from matching characters to skip sections of the text, making it more efficient than naive approaches.
It does this by:

Building a "partial match table" based on the word W
Whenever a mismatch occurs, it uses the table to determine how far to skip in the text (instead of just skipping 1 character)

This allows it to quickly "recover" from mismatches and often skip large sections of the text, making it very efficient.
The end result is an algorithm with linear time complexity (proportional to the lengths of the input strings).

So in short, the key insight is to pre-compute information from the word and use that to efficiently "recover" from mismatches and skip sections of the text, making it faster than naive approaches.