Knuth-Morris-Pratt法
P[7] (=
b
)で不一致が検出されたとき
前のテキストは
aaaaaa
であることが既知
P[6] (=
a
)の比較をやり直せばよい
不一致が検出されたときに比較をやりなおすべきPの文字の位置をあらかじめ「失敗関数」として計算
無駄な比較を繰り返さないようにする
