There are no translations available.
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.