Algorytm Karpa-Rabina
Z Wikipedii
Algorytm Karpa-Rabina jest algorytmem dopasowania wzorca - służy do lokalizowania w tekście określonego podciągu.
Dany jest wzorzec ![x[1\ldots m]](../../../math/c/f/4/cf46a47ddc97a609b348298b13a4aba3.png)
(złożony z m znaków) oraz przeszukiwany ciąg ![y[1\ldots n]](../../../math/3/2/6/32625fd7a0a169a3ad2d171560953619.png)
(złożony z n znaków; n > m). Problem dopasowania wzorca polega na znalezieniu takiego indeksu i, dla którego ![y[i\ldots i+m] = x[1\ldots m]](../../../math/3/f/e/3fea1b819e3b5f7eb8482e34440ad2cb.png)
.
W algorytmie Karpa-Rabina wykorzystuje się funkcję mieszającą h. Przeglądane są wszystkie podciągi ![y_i := y[i\ldots i+m]](../../../math/d/a/e/dae8be1b318b9fcdc00fde23b0491d52.png)
dla ![i \in [1\ldots n-m]](../../../math/9/5/e/95e03d0e723629b8a3375d1529d94bf3.png)
, ale bezpośrednie porównania podciągu yi z x (które jest bardzo kosztowne) ma miejsce tylko wtedy, gdy h(yi) = h(x).
O efektywności algorytmu decyduje konstrukcja funkcji mieszającej h - powinna istnieć funkcja N która niskim kosztem wyznacza h(yi + 1) na podstawie znanej już wartości h(yi). W praktyce traktuje się tekst, jako liczbę zapisaną w systemie o określonej podstawie (najczęściej biorąc jako wartości cyfr kody ASCII znaków).
Oczekiwany koszt obliczeniowy jest rzędu O(m + n).
Pseudokod (dane x, y, n, m):
![Sx \larr h(x[1\ldots m])](../../../math/e/c/1/ec13dc00bee328c984c1456a8ce41ff2.png)
![Sy \larr h(y[1\ldots m])](../../../math/e/e/1/ee1df260394634e9eac369782260a18d.png)
- for
to n − m do
- begin
- if Sx = Sy then
- begin
- porównaj ciąg z podciągiem
![y[i\ldots i+m]](../../../math/0/c/8/0c830be8412100a25996ffed27018802.png)
- if wynik porównania prawdziwy then zwróć indeks i
- end
![Sy \larr N(Sy, y[i], y[i+n])](../../../math/5/9/9/5992cb34d4782d008dae84b7d26f8bf6.png)
- if Sx = Sy then
- end
- begin
