スライド 1

8 にいて 9 (エッジ e)を見たとき, failure(8) で 4 が返り、
g(4, 'e') = False → failure(4) で 0 が返り、g(0, 'd') = 7.
よって failure(9) = 7
1 にいるとき 2 (エッジ b の先) の 2 にお
ける failure(2) を決める。failure(1) で 0
が返り、g(0, 'b') = 3。よってfailure(2)
=3
b
a
0
1
b
c
3
2
ab
d
8
5
7
d
幅優先探索で、着目している状態の次の遷移先
の failure 関数の値を決める。よって 0 にいる
ときは深さ 1 の状態 1, 3, 7 について検討する。
深さ1に位置する全ての failure 関数の向かう先
は 0 (failure 関数では必ず1以上浅い状態へ遷
移するが、深さ1では浅い状態は 0 しかない)
e
9
10
abcde
3 にいるとき 4 (エッジc の先) の
failure(4) を決める。failure(3) で 0 が返
り、g(0, 'c') = False. よって falure(4)
=0
4
bc
a
d
c
b
6
bab
同様に、3にいるとき 5 (エッジaの先) の
5 における failure(5) を決める。
failure(3) で 0 が返り、g(0, 'a') = 1.
よって failure(5) = 1