ALGORYTM KNUTH-MORRIS-PRAT

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 Naiwnym 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 { 0≤k<j: wzorzec[1..k] jest sufiksem wzorzec[1..j]}.

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 Naiwnego.

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;

NS - obliczanie tablicy

P[0]:=0; P[1]:=0; t:=0;

j:=2 .. m

(t>0) and wzorzec[t+1]<>wzorzec[j]

wzorzec t[i+1]=wzorzec[j]

T N

t:=t+1;

P[j]:=t;

NS - algorytm KMP

i:=1; j:=0

i<=n-m+1;

((j<m) and wzorzec[j+1]=tekst[i+j])

j:=j+1;

T j=m N

IntToStr(i)

i:=i+max(1,j-P[j]);

program Algorytm_KMP;

uses

Forms,

SysUtils,

math;

{$R *.RES}

{$Apptype console}

var

m,n,i,j,t:Integer;

wzorzec:String;

tekst:String;

P: array of Integer;

begin

writeln('Podaj tekst');

readln(tekst);

writeln('Podaj wzorzec');

readln(wzorzec);

n:=length(tekst);

m:=length(wzorzec);

SetLength(P,m+1);

//algorytm obliczania tablicy P

P[0]:=0; P[1]:=0; t:=0;

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;

//Algorytm KMP (Knutha-Morrisa-Pratta)

writeln('Indeksy poczatkow wzorca w tekscie');

i:=1; j:=0;

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)));

i:=i+max(1,j-P[j]);

end;

readln;

end.

j:=P[j];

---