Algorytm Rabina-Karpa skupia się zamiast tego przyspieszeniu działania linii kodu od 3 do 6, co będzie rozważane w następnych paragrafach.
Użycie funkcji skrótu do zmiennego przeszukiwania podciągu Zamiast dążyć do bardziej wyrafinowanego przeskakiwania, algorytm Rabina-Karpa przyspiesza porównywanie szukanego wzorca do podciągów w tekście za pomocą funkcji skrótu. Funkcja skrótu przerabia każdy ciąg liter na postać numeryczną nazywaną skrótem (ang. hash). Algorytm Rabina-Karpa wykorzystuje fakt, że jeżeli dwa teksty są równe, ich skróty też są równe. Implikacja odwrotna nie zachodzi jednak – dla dwóch różnych tekstów mogą się zdarzyć dwa równe skróty. Trzeba zatem porównać także teksty, jeśli wartości skrótów są równe:
1 function RabinKarp(string s[1..n], string sub[1..m]) 2 hsub := hash(sub[1..m]) 3 hs := hash(s[1..m]) 4 for i from 1 to n 5 if hs = hsub 6 if s[i..i+m-1] = sub 7 return i 8 hs := hash(s[i+1..i+m]) 9 return not found
Linie 2, 3, 6 i 8 wymagają Ω(m) czasu każda. Jednakże linie 2 i 3 są wykonane tylko raz a linia 6 jest uruchamiana tylko gdy wartości skrótu są równe. Linia 5 jest wykonywana n razy, ale wymaga stałego czasu.