Opis wyszukiwania wzorców w tekście abccab Wyszukiwanie wzorców w tekście abccab Węzeł Tekst do przeglądnięcia Wyjście programu:Pozycja w słowie Przejście Wyjście programu () abccab rozpoczęcie w korzeniu (a) bccab a:1 () do potomka (a) Obecny węzeł (ab) ccab ab:2 (a) do potomka (ab) Obecny węzeł (bc) cab bc:3, c:3 (ab) do sufiksu (b) do potomka (bc) Obecny węzeł, Węzeł sufiksowy ze słownika (c) ab c:4 (bc) do sufiksu (c) do sufiksu () do potomka (c) Obecny węzeł (ca) b a:5 (c) do potomka (ca) Węzeł sufiksowy ze słownika (ab) ab:6 (ca) do sufiksu (a) do potomka (ab) Obecny węzeł
Algorytm tworzenia automatu Dane są trzy funkcje:
NEXT(węzeł, litera) – funkcja przejścia definiująca, z którym węzłem jest połączony przez krawędź etykietowaną literą, np. NEXT("bc", 'a') ⇒ "bca", natomiast NEXT("ca", 'b') ⇒ NIL. FAIL(węzeł) – funkcja określająca węzeł połączony przez krawędź fail. OUTPUT(węzeł) – zbiór napisów powiązanych z węzłem.
Algorytm składa się z dwóch głównych kroków: utworzenia drzewa trie, dla wszystkich napisów na tym etapie ustalane są wartości funkcji NEXT oraz OUTPUT; uzupełnienie krawędzi fail (czyli określenie funkcji FAIL).