algorytm.org

Algorytm KMP (Knutha-Morrisa-Pratta)

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 KMP (Knutha-Morrisa-Pratta)
Ocena użytkowników:***** / 25
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 26 lipca 2005 18:52

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.

W algorytmie N podczas przeszukiwania początek wzorca przesuwamy zawsze o jeden, podczas gdy możliwe jest czasami dużo większe przesunięcie. Informacja o tym przesunięciu będzie zawarta w tablicy P o rozmiarze wzorca. Niech P[j], gdzie j>1, będzie maksymalną długością właściwego sufiksu (końcówki) słowa wzorzec[1..j], będącego jednocześnie jego prefiksem (początkiem). Co można zapisać formalnie:

P[j]= \max \left\{ 0 \leq; k < j: wzorzec[1..k] \text{jest sufiksem} wzorzec[1..j] \right\}
Wzór ten na pierwszy rzut oka może wydawać się skomplikowany. Przeanalizujmy więc go na prostym przykładzie.

Przykład:

wzorzec=abbabcabb
obliczmy teraz dla takiego wzorca tablicę P
Przyjmujemy P[0]=0 oraz P[1]=0, następnie:
P[2]=0, P[3]=0,
P[4]=1, gdyż a (początek wzorca) jest sufiksem abba (wzorzec[1..4])
P[5]=2, gdyż ab (początek wzorca) jest sufiksem abbab (wzorzec[1..5])
P[6]=0,
P[7]=1, gdyż a (początek wzorca) jest sufiksem abbabca (wzorzec[1..7])
P[8]=2, gdyż ab (początek wzorca)jest sufiksem abbabcab (wzorzec[1..8])
P[9]=3, gdyż abb (początek wzorca) jest sufiksem abbabcabb (wzorzec[1..9])

Algorytm obliczania tablicy P:
P[0]:=0; P[1]:=0; t:=0; //z założenia
for j:=2 to m do
begin
  while (t>0) and (wzorzec[t+1]<>>wzorzec[j]) do t:=P[t];
  if wzorzec[t+1]=wzorzec[j] then t:=t+1;
  P[j]:=t;
end;

Jeśli tablica P jest już policzona, to problem wyszukiwania wzorca można efektywnie rozwiązać za pomocą algorytmu KMP, którego struktura jest podobna do struktury algorytmu N.
while i<=n-m+1 do
begin
  j:=P[j];
  while ((j<m)and(wzorzec[j+1]=tekst[i+j])) do j:=j+1;
  if j=m then writeln((IntToStr(i))); //wypisanie indeksu, w którym istnieje dopasowanie
  i:=i+max(1,j-P[j]);
end;

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 5
Bartosz BednarczykC/C++Rozwiązanie z użyciem STLa, dynamiczna alokacja, KMP dla sklejenia wzorca i tekstu, słowa numerowane od 1
.cpp
.cpp
***** / 6
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
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: 15 sierpnia 2012 13:28
Komentarze
photo
+3 # emil3566 2012-02-04 17:42
Ojojoj , nie zgodzę się z tym co tutaj jest napisane , dobrze wytłumaczone ale da się to zrobić w mniej zagmatwany sposób !!!

Wystarczy puścić do funkcji wypełniającej tablicę P , słowo które wygląda tak:
wzorzec#słowo (# = hash , jakiś znak specjalny)
i wtedy wystarczy zliczyć ilość wystąpień wzorzec.length() w tablicy P (robimy to podczas jej wypełniania) i mamy odp :)

Jeżeli to komuś pomoże to bardzo proszę ;) mniej do zapamiętania
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # 123navyblue 2012-09-08 10:03
Tak jest prościej ale nie zawsze lepiej.
Trzeba pamiętać, że czasami nie ma możliwości użycia tak zwanego hasha. Poza tym, sklejenie wzorca z bardzo dużym tekstem mogłoby być mało wydajne pod względem użycia pamięci.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # catalyst 2013-08-03 21:47
Nie ma tu żadnej funkcji "wypełniającej tablicę P", więc ciężko "puścić" cokolwiek do czegoś co nie istnieje. Twój komentarz jest zdecydowany bardziej zagmatwany niż sam artykuł
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz