• 右からk文字だけ一致したときにその次にどこから比較を再開すればよいかをあらかじめパタンから計算
• 2個の表を用意
  • d1 -- 右端で不一致が検出されたときの、移動数[不一致文字]の表
  • d2 -- 右からk文字目で不一致が検出されたときの、移動数[不一致位置]の表
• 先の例の場合、d1['a'] = 1, d2['c'] = d1['d'] = ... = 8である。