方を様々に変更して検索する用途に向く。オートマトンを生成する。1文字ずつ順番に見て、前計算結果に従い遷移する。$O(|S|+m+マッチ数)$もう少し詳細failureの構築Trie木を構築後、各ノードに対し、検索失敗時に戻るノード(failure)を特定する。幅優先探索で根から近い方から埋めていくことで、遡る時に訪れるfailureが既に確定していることを保証できる。出現していることがわかる。failureリンク。その後'bcde'が見つかって終わりになる。実際は'cd'も含まれるのに、'cd'のノードは一回も訪れられない。探索中に訪れるのは「最も長く一致しているノード」であるためである。...」を根まで遡って調べると見つけることが出来る。上例では、'abcd'に訪れたとき、そのfailureのfailureが'cd'のため、そこで見つけることができる。実際にそんなことをやっていると時間がかかるので、failureを構築する過程で前計算しておく。各ノードが「自身からfailureを遡っていったときに見つかる文字列リスト」matchを持つ。登録しておくfailure構築時、自身のmatchに、自身のfailureのmatchを全て加える根から近い方から構築するので、failureのmatchには、既にfailureのfailure以前のmatchが含まれているこうしておくと、'abcd'のノードのmatchに'cd'が登録されており、見つけることが出来る。辿る過程でmatchを参照していく。