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
© Copyright 2024 ExpyDoc