algorytm.org Algorithms Przetwarzanie tekstu Algorytm N (naiwny)  
Home AlgorithmsData structuresAlgorithmics turorialPractiseDesign patternsIT Law SitemapPortal historyContributors ForumToolsWrite an articleSearch 

Algorytm N (naiwny)
User Rating: / 4
PoorBest 
Written by Tomasz Lubiński   
Monday, 25 July 2005 22:44
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.



.

Author Progam language Comment Download Rate
Tomasz Lubiński C/C++
Implementation in C/C++
/ 0
Tomasz Lubiński Delphi/Pascal
Implementation in Delphi/Pascal
/ 0
Tomasz Lubiński Java
Implementation in Java
/ 0
 
Add your implementation for this algorithm
  • Login first
File:
Progam language:
Comment:
  To be able to add your implementation, login first



Last Updated on Monday, 07 June 2010 23:13
 

Add comment







Danation
Donate us


RSS Channels
Articles
Implementations
Comments
Forum


Bookmarks








Poll
Czy znalazłeś na stronach www.algorytm.org to czego szukałeś?
 

www.algorytm.org (c) 2000-2010