• 最速といわれるテキスト検索アルゴリズム
• 文字比較回数が文字列長より少なくてすむ
  • KMP法ではテキストの文字をすべて比較しなければならない
• パタンの右端からマッチを調べる
  • 1回目の文字比較でT[m] = cであることがわかる
  • cはPに含まれていないので2回目の比較はT[m+1]の先から調べればよい