Algorytm Aho-Corasick — część 6

{ wykonanie fragmentu procedury Aho-Corasick-wyszukiwanie } for litera in alfabet: { dla liter alfabetu, dla których NEXT jest nieokreślony (NIL) } if NEXT(węzeł, litera) = nil then DETNEXT(węzeł, litera) := DETNEXT(FAIL(węzeł), litera) { lub skopiowanie istniejącego przejścia } else x = NEXT(węzeł, litera) DETNEXT(węzeł, litera) = x dodaj x do kolejki end end end end

Wówczas algorytm wyszukiwania upraszcza się do:

procedure Aho-Corasick-wyszukaj-w-deterministycznym(napis, trie) begin węzeł = korzeń drzewa trie for i := 1 to długość napisu do litera := napis[i] węzeł := DETNEXT(węzeł, litera)

if OUTPUT(węzeł) <> nil then wypisz pozycję i wypisz wszystkie wartości ze zbioru OUTPUT(węzeł) end end end

Bibliografia

Linki zewnętrzne Implementacja w Perlu

Darmowa implementacja w C

Kategoria:Algorytmy tekstowe