algorytm.org

Algorytm N (naiwny)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm N (naiwny)
Ocena użytkowników:***** / 27
SłabyŚwietny 
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.

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.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Jacek GzelC#
.cs
.cs
***** / 0
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 16
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 6
Tomasz LubińskiJava
.java
.java
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 lipca 2012 18:28
Komentarze
photo
-7 # Henryk 2010-09-04 14:25
Szukam algorytmu, względnie kodu dla Delphi, który przeszukałby określony plik tekstowy i po wyszukaniu zadanego wyrazu w Edit1.text wpisałby do Memo jako pełne linie w których dany wyraz występuje

mój adres:
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz