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