�ݺ�ߣ

Algorytm Knutha-Algorytm Knutha-
Morrisa-PrattaMorrisa-Pratta

TWÓRCYTWÓRCY
Został stworzony przez Vaughana Pratta i
Donalda Knutha oraz niezależnie przez J.
H. Morrisa w 1977, jednakże wszyscy trzej
opublikowali go wspólnie.

TWÓRCYTWÓRCY
DONALD KNUTH VAUGHAN PRATT

Czym jest algorytm KMP?Czym jest algorytm KMP?
Najprościej mówiąc jest to algorytm
wyszukiwania wzorca w tekście.
Wykorzystuje fakt, że w przypadku
wystąpienia niezgodności ze wzorcem,
sam wzorzec zawiera w sobie informację
pozwalającą określić gdzie powinna się
zacząć kolejna próba dopasowania,
pomijając ponowne porównywanie już
dopasowanych znaków. Dzięki temu w
znaczny sposób zyskujemy na czasie.

Przykładowe działaniePrzykładowe działanie
Na początku potrzebujemy wzorca W i
tekstu T. Mamy też dwie zmienne
pomocnicze t oraz w, które opisują
odpowiednio pozycję w T, od której
rozpoczyna się aktualne częściowe
dopasowanie, oraz indeksu W
oznaczającego następny rozpatrywany
znak wzorca.

Przyjmimy:
w=012345678
W=ABBCCBABC
T=ABC
t=012

• Zaczynamy! Na początku porównujemy znaki
W do „równoległych” im znaków z T,
przechodząc dalej, jeżeli wszystko się
zgadza. Jendkaże widzimy, że W[3]=‘B’,
natomiast T[3]=‘C’ . W tym momencie
ponieważ widzimy, że na pozycjach 1-6 nie
występuje ‘A’ przesuwamy się na w=1 i
zaczynamy dopasowywanie od początku.
Dzięki temu otrzymujemy niemal
natychmiastowe dopasowanie, które okazuje
się prawidłowe.

PSEUDOKOD CZĘŚCIPSEUDOKOD CZĘŚCI
SZUKAJĄCEJSZUKAJĄCEJ
algorytm kmp_search:
wejście: tablica znaków, S (przeszukiwany tekst)
tablica znaków, W (szukane słowo)
wyjście: liczba całkowita (liczona od zera pozycja w S,
na której znaleziono W)
zdefiniowane zmienne:
liczba całkowita, m = 0 (początek bieżącego
dopasowania w S) liczba całkowita, i = 0 (pozycja bieżącego
znaku w W)
tabela liczb całkowitych, T (tabela liczona gdzie indziej)
dopóki m + i jest mniejsze niż długość S, wykonuj:
jeżeli W[i] = S[m + i], niech i = i + 1
jeżeli i równe jest długości W, zwróć m
w przeciwnym przypadku,
niech m = m + i - T[i], oraz jeśli i > 0, niech i = T[i]
(jeśli dotrzemy tu, tzn., że przeszukaliśmy bezskutecznie
cały S)
zwróć długość S

TABLICA CZĘŚCIOWYCHTABLICA CZĘŚCIOWYCH
DOPASOWAŃDOPASOWAŃ
„Celem tej tabeli jest umożliwienie algorytmowi nie
dopasowywania żadnego znaku z S więcej niż raz.
Kluczową obserwacją natury liniowego
poszukiwania, która na to pozwala, polega na tym,
że mając porównany pewien segment głównego
ciągu znaków z początkowym fragmentem wzorca,
wiemy dokładnie, w których miejscach mogłoby
zacząć się nowe potencjalne dopasowanie przed
bieżącą pozycją. Inaczej mówiąc, występuje tutaj
"wstępne poszukiwanie" samego wzoru i zestawu
wszelkich możliwych pozycji do powrotu, które
pomijają złe wybory, nie zabierając zasobów.”

PSEUDOKOD ALGORYTMUPSEUDOKOD ALGORYTMU
BUDOWANIA TABELIBUDOWANIA TABELIalgorytm kmp_table:
Dane wejściowe:
tablica znaków, W (słowo, które będzie analizowane)
tablica liczb całkowitych, T (która ma być zapełniona)
Dane wyjściowe:
nic (ale podczas działania zapełniana jest tablica wejściowa) Zdefiniowane zmienne:
liczba całkowita, i = 2 (aktualna pozycja, jaką przetwarzamy w tablicy T)
liczba całkowita, j = 0
(liczony od zera indeks tablicy W, w której ma być umieszczona kolejna litera szukanego ciągu znaków)
(pierwszych kilka wartości to stałe, ale inne, niż algorytm mógłby sugerować)
niech T[0] = -1, T[1] = 0
dopóki i jest mniejsze od długości w, rób:
(pierwsza opcja: ciąg znaków jest dłuższy)
jeżeli W[i - 1] = W[j], niech T[i] = j + 1, i = i + 1, j = j + 1
(druga opcja: ciąg znaków nie jest dłuższy, ale nie możemy się cofnąć)
jeśli j > 0, niech j = T[j]
(trzeci przypadek: wyczerpuje się zasób kandydatów, Zauważ, że j=0)
niech T[i] = 0, i = i + 1

ALGORYTMU KMP DLAALGORYTMU KMP DLA
JĘZYKA C++JĘZYKA C++
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#ifdef __cplusplus
int max (int value1, int value2);
int max(int value1, int value2)
{return ( (value1 > value2) ? value1 : value2); }
#endif
void main(void)
{
char wzorzec[100];
char tekst[2000];
int m,n,i,j,t;
int P[100];//maksymalna dlugosc wzorca to 100 symboli
printf("Podaj tekstn");
scanf("%s", tekst);
printf("Podaj wzorzecn");
scanf("%s", wzorzec);
n=strlen(tekst);
m=strlen(wzorzec);
printf("Indeksy poczatku wzorca w tekscien");
//obliczenie tablicy P
P[0]=0; P[1]=0; t=0;
for (j=2; j<=m; j++)
{
while ((t>0)&&(wzorzec[t]!=wzorzec[j-1])) t=P[t];
if (wzorzec[t]==wzorzec[j-1]) t++;
P[j]=t;
}
//algorytm KMP
i=1; j=0;
while (i<=n-m+1)
{
j=P[j];
while((j<m)&&(wzorzec[j]==tekst[i+j-1])) j++;
if (j==m) printf("%dn",i);
i=i+max(1,j-P[j]);
}
getch();
return;
}

ZŁOŻONOŚĆZŁOŻONOŚĆ
OBLICZENIOWAOBLICZENIOWA
ALGORYTMU KMPALGORYTMU KMP
Złożoność części szukającej algorytmu KMP to O(k), gdzie k to
długość tekstu, w którym będziemy szukać wzorca. Natomiast
część budowania tabeli ma złożoność mieszczącą się w O(n),
gdzie n to długość wzorca. Jeżeli więc algorytm składa się z 2
części mających złożoności odpowiednio O(k) i O(n), to całkowita
złożoność będzie wynosiła O(k+n). Widzimy również, że ten
algorytm ma taką przewagę nad algorytmem naiwnym
wyszukiwania wzorca, że może pomijać większą część znaków. A
skoro mniej musi się „cofać”, to szybciej się wykonuje.

ALGORYTM KMP NAALGORYTM KMP NA
OLIMPIADZIEOLIMPIADZIE
INFORMATYCZNEJINFORMATYCZNEJ
Istnieje wiele zadań olimpijskich, które da się
rozwiązać za pomocą algorytmu KMP. Oto niektóre z
nich:
PUNKTY - XII OI
PALINDROMY - II OI
MEGACUBE - 5 OBÓZ OI
SZABLON - XII OI
http://pl.spoj.com/problems/KMP/ - SPOJ

�ݺ�ߣ

Suchy

Recommended

More Related Content

Viewers also liked (16)

Suchy