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

Komentarze