Wpisany przez Tomasz Lubiński,
25 lipca 2005 22:44
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.
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.
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;
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.
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Jacek Gzel | C# | .cs | .cs | ***** / 0 | |
Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 7 | |
Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 6 | |
Tomasz Lubiński | Java | .java | .java | ***** / 4 |
Poprawiony: 30 lipca 2012 18:28
mój adres: kallas555wp.pl