Uzupełnianie krawędzi fail Drzewo trie przeglądane jest poziomami (wszerz) – mając zdefiniowane FAIL dla wszystkich węzłów na poziomie P-1 i wcześniejszych, można znaleźć wartości FAIL oraz OUTPUT dla węzłów z poziomu P.
W pierwszym kroku uzupełnia się FAIL dla węzłów z poziomu pierwszego (czyli następników korzenia), po czym przeglądane są kolejne poziomy.
procedure Aho-Corasick-tworzenie-fail(trie) kolejka := pusta kolejka korzeń := korzeń drzewa trie
{ etap 1 } for litera in alfabet do węzeł = NEXT(korzeń, litera) if węzeł <> nil then { powiąż krawędzią fail } FAIL(węzeł) = korzeń
dodaj węzeł do kolejki else { określenie funkcji NEXT korzenia dla każdej litery } NEXT(korzeń, litera) = korzeń end end
{ etap 2 } while kolejka nie pusta do węzeł = weź z kolejki for litera in alfabet do następnik = NEXT(węzeł, litera) if następnik <> nil then dodaj następnik do kolejki
x := FAIL(węzeł) while NEXT(x, litera) = nil do x := FAIL(x) end
FAIL(następnik) := NEXT(x, litera) OUTPUT(następnik) := OUTPUT(następnik) + OUTPUT(NEXT(x, litera)) end end end
Algorytm wyszukiwania procedure Aho-Corasick-wyszukiwanie(napis, trie) begin węzeł = korzeń drzewa trie for i := 1 to długość napisu do litera := napis[i]
while NEXT(węzeł, litera) = nil do węzeł := FAIL(węzeł) end