Więc jedynym punktem mogącym negatywnie wpłynąć na złożoność algorytmu jest linia 8.
Jeśli wyliczymy w sposób naiwny wartość skrótu dla podciągu s[i+1...i+m], zajmie to Ω(m) czasu, a ponieważ linia ta jest wykonywana przy każdym obiegu pętli, cały algorytm będzie miał złożoność czasową Ω(mn), czyli tyle ile najmniej wydajne algorytmy naiwne. Sztuczka polega na wyliczeniu aktualnego skrótu na podstawie skrótu wyliczonego w poprzednim obiegu pętli. Do tego służy algorytm postępującego skrótu.
Najprostsza wersja działa według takiej zasady: wyznacza się wartość każdego znaku w podciągu, następnie wylicza się skrót według wzoru
Ta prosta funkcja skrótu ma niestety niezbyt równomierny rozkład, co powoduje, że linia 6 jest wykonywana o wiele częściej niż w innych bardziej wyrafinowanych algorytmach postępującego skrótu.
Funkcje skrótu będące w użyciu Kluczem wydajności algorytmu Karpa-Rabina jest efektywne wyliczanie wartości skrótu kolejnych podciągów tekstu. Jeden z wydajnych algorytmów postępującego skrótu traktuje podciągi jako numery o pewnej bazie. Bazą zazwyczaj jest jakaś duża liczba pierwsza. Np.: dla podciągu „hi” wartość skrótu wynosi 104 * 101^1 + 105 * 101^0 = 10609 (kod ASCII dla h wynosi 104, a dla i – 105).