Algorytm Karpa-Rabina jest algorytmem dopasowania wzorca – służy do lokalizowania w tekście określonego podciągu. Został stworzony w 1987 roku przez Michaela O. Rabina i Richarda Karpa.
Dany jest wzorzec (złożony z znaków) oraz przeszukiwany ciąg (złożony z znaków; ). Problem dopasowania wzorca polega na znalezieniu takiego indeksu dla którego
W algorytmie Karpa-Rabina wykorzystuje się funkcję mieszającą Przeglądane są wszystkie podciągi dla ale bezpośrednie porównania podciągu z (które jest bardzo kosztowne) ma miejsce tylko wtedy, gdy
O efektywności algorytmu decyduje konstrukcja funkcji mieszającej – powinna istnieć funkcja która niskim kosztem wyznacza na podstawie znanej już wartości 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).
Oczekiwana złożoność obliczeniowa jest rzędu
Pseudokod (dane ):
for to do begin if then begin porównaj ciąg z podciągiem if wynik porównania prawdziwy then zwróć indeks end
end