Podstawowym problemem dotyczącym tekstów jest problem wyszukiwania wzorca. Polega on na znalezieniu wszystkich wystąpień tekstu wzorzec, w tekście tekst. Przyjmujemy ponadto, że: |wzorzec|=m, |tekst|=n oraz n≥m.

Oto schemat najprostszego algorytmu rozwiązującego problem wyszukiwania wzorca:
while i<=n-m+1 do
begin
 j:=0; while ((wzorzec[j+1]=tekst[i+j])and(j<m)) do j:=j+1;
 if j=m then writeln((IntToStr(i))); //wypisanie indeksu, w którym istnieje dopasowanie
  i:=i+1;
end;

W algorytmie tym zwiększamy w kolejnych iteracjach zmienną i, która wskazuje miejsce rozpoczęcia porównywania wzorca z tekstem, które jest realizowane w zagnieżdżonej pętli while. Sygnałem odnalezienia dopasowania jest zrównanie zmiennej j ze zmienną m. Wynika to z faktu, iż zmienne te będą równe dopiero po m-krotnym wykonaniu zagnieżdżonej pętli while, tzn gdy wyjście z niej nastąpi pod wpływem nie spełnienia warunku j<m. W praktyce oznacza to, że począwszy od indeksu i wzorzec pasuje do tesktu.

Przykład
teskt=bbabbbaabb, n=10
wzorzec=aab, m=3
dla i=1 nie nastąpi wejście do zagnieżdżonej pętli while, nie jest również spełniony warunek if.
dla i=2 nie nastąpi wejście do zagnieżdżonej pętli while, nie jest również spełniony warunek if.
dla i=3 nastąpi wejście do zagnieżdżonej pętli while, ale dla j=1 nastąpi wyjście, po tym wyjściu warunek if będzie niespełniony,
dla i=4..6 nie nastąpi wejście do zagnieżdżonej pętli while, nie jest również spełniony warunek if.
dla i=7 nastąpi wejście do zagnieżdżonej pętli while, która wykonywana będzie aż do j=3, po tym wyjściu warunek if jest spełniony tzn. znaleziono dopasowanie.
dla i=8 nie nastąpi wejście do zagnieżdżonej pętli while, nie jest również spełniony warunek if.
dla i=9 nie jest spełniony główny warunek, algorytm zostaje zakończony.

Komentarze