Wyszukiwanie wzorca

Problem znajdowania wzorca w tekście

Rafał Nowak

Niech dany będzie wzorzec — słowo $m$ literowe $P[1..m]$ oraz tekst — słowo $n$ literowe $T[1..n]$.
Na przykład:

Problem polega na znalezieniu miejsc występowania wzorca $P$ w tekście $T$.
Powiemy, że wzorzec $P$ występuje na miejscu $i$, jeśli

(1)

\begin{align} P[1+j]=T[i+j] \quad \text{dla} \quad j=0, 1, \ldots, m-1 \end{align}

Dla powyższego przykładu, wzorzec $P$ występuje aż na trzech pozycjach. Zaznaczono je poniżej kolorem zielonym.

Algorytm naiwny

Pierwsze rozwiązanie danego problemu, jakie przychodzi do głowy, to naiwny sposób sprawdzania dla każdej pozycji $i$, czy dany wzorzec występuje na tej pozycji.

Sprawdzanie, czy wzorzec występuje na danej pozycji

czy_wystepuje( i )
  j := 0
  while j<m and P[1+j]=T[i+j] do j := j+1
  if j=m then return true
  else return false;

Algorytm naiwny

for i from 1 to n-m+1 do
  if ( czy_wystepuje( i ) ) then wypisz i;

Analiza algorytmu

Przedstawiony algorytm bardzo łatwo poddać analizie jego złożoności. Mianowicie, pojedyncza operacja czy_wystepuje(..) może kosztować, w najgorszym wypadku aż $m$ porównań. Ponieważ algorytm wywołuję ją dokładnie $n-m+1$ razy, więc złożoność czasowa algorytmu naiwnego wynosi $\mathcal{O}(n\cdot m)$.
Łatwo podać najgorszy przykład danych, mianowicie jeśli tekst i wzorzec składają się z tylko jednej i tej samej litery, algorytm wykonuje najwięcej porównań: