Knuth-Morris-Pratt法の例
KMP example
P = “
abcaba
” の場合
5 → 1 の遷移
Translation from 5 to 1
5の状態でテキストの最後が
abca
であることが既知
→2の状態まで戻れる
5から6に遷移できない場合
次の文字は
b
でない
→1の状態まで戻れる
