KMP 文字列照合
パターン照合で 一度照合した文字を二度と見直さない ── KMP 法の賢い「ずらし方」を可視化します。
0
部分一致表（失敗関数）── パターンの各位置までで「先頭と一致する最長の長さ」
テキスト位置 i
0
パターン位置 j
0
見つかった位置
—
照合のようす
テキストの中からパターンを探すとき、素朴な方法は不一致のたびにパターンを 1 つずらして最初から比べ直します。
KMP 法は事前に 部分一致表（失敗関数）を作っておき、不一致が起きたとき 「すでに一致していた部分」を手がかりに パターンを大きくジャンプさせます。 テキストの読み取り位置は絶対に戻らない ── だから線形時間 O(テキスト長 + パターン長) で探せます。
KMP 法は事前に 部分一致表（失敗関数）を作っておき、不一致が起きたとき 「すでに一致していた部分」を手がかりに パターンを大きくジャンプさせます。 テキストの読み取り位置は絶対に戻らない ── だから線形時間 O(テキスト長 + パターン長) で探せます。
いま何をしている？
ここがポイント
- 素朴法は不一致のたびに巻き戻して比べ直す（最悪 O(テキスト長 × パターン長)）。
- KMP は 部分一致表で「どこまで一致が活かせるか」を知り、無駄な比較を飛ばす。
- テキストの読み取り位置 i は決して戻らない ── これが線形時間の理由。