Szukanie podsłów

Pokażemy, jak sprawdzać, czy \( z \) występuje w \( x \).

Używając drzewa sufiksowego (czas \( O(m) \))

Idziemy od korzenia w dół czytając kolejne symbole \( z \), czasami posuwamy się po wewnętrznej etykiecie pewnej krawędzi. Zbiór wystąpień odpowiada zbiorowi liści w poddrzewie węzła, do którego doszliśmy. Jeśli po drodze utknęliśmy i nie dało się dalej schodzić po drzewie, oznacza to, że \( z \notin Subwords(x) \)

Używając tablicy sufiksowej (czas \( O(m \log n) \))

Możemy sprawdzić, czy \( z \) jest prefiksem \( i \)-tego sufiksu w czasie \( O(m) \). Korzystając z tego, wykonujemy rodzaj binarnego szukania. W ten sposób znajdujemy pierwszy sufiks, którego prefiksem jest z. Jeśli jest taki sufiks, to \( z \in Subwords(x) \). W przeciwnym wypadku z nie jest podsłowem x.

Podobnie znajdujemy ostatni sufiks. Zbiór wystąpień odpowiada przedziałowi w tablicy \( SUF \) między obliczonymi pierwszym i ostatnim sufiksem zaczynającym się od z.