ALG!3

8.2. Nowe algorytmy poszukiwań 213

Analogiczny przykład znajduje się na rysunku 8-5.

8.2. Nowe algorytmy poszukiwań 213

Rys. fi - 5.

„Przesuwanie się " wzorca w

i^const

i i=const

algorytmie K-M-P (2)

■I ⁰ I ¹ I ¹ I ⁰ l"i"R

10 1

j-3

i

i

Tym razem niezgodność wystąpiła na pozycji j-3. Dokonując - podobnie jak poprzednio - „przesuwania” wzorca w prawo, zauważamy, iż jedyne możliwe nałożenie się znaków wystąpi po przesunięciu o dwie pozycje w prawo - czyli dla /=/. Dodatkowo okazuje się, że znaki za kreską też się pokryły, ale o tym algorytm „dowie się” dopiero podczas kolejnego testu zgodności na pozycji i.

kmp.cpp

Dla potizeb algorytmu K-M-P konieczne okazuje się wprowadzenie tablicy przesunięć intshift[MJ. Sposób jej zastosowania będzie następujący: jeśli na pozycji / wystąpiła niezgodność znaków, to kolejną wartością ; będzie shifiJjJ. Nie wnikając chwilowo w sposób inicjalizacji tej tablicy (odmiennej oczywiście dla każdego wzorca), możemy natychmiast podać algorytm K-M-P, który w konstrukcji jest niemal dokładną kopia^ algorytmu typu brate-force:

int kmptchar 'w.char ‘tl

(

int i,j,N=strlen(t); for(i=0,j=0;i<N Si j<M;i++,j++) while((j >-C) S 4 (t [ i ] !-w[j])) j=shift[j1; if (j—M) return i-M; else

return -1;

)

Szczególnym przypadkiem jest wystąpienie niezgodności na pozycji zerowej: z założenia niemożliwe jest tu przesuwanie wzorca w celu uzyskania nałożenia się znakowe Z tego powodu chcemy, aby indeks j pozostał niezmieniony przy jednoczesnej progresji indeksu i. Jest to możliwa do uzyskania, jeśli umówimy się, że shiftfO] zostanie zainicjowany wartością-/. Wówczas podczas kolejnej iteracji pętli for nastąpi inkrementacja / i j, co wyzeruje nam j.

Pozostaje do omówienia sposób konstrukcji tablicy shift[MJ. Jej obliczenie powinno nastąpić przed wywołaniem funkcji kmp, co sugeruje, iż w przypadku wielokrotnego poszukiwania tego samego wzorca nie musimy już powtarzać