Z tej prostej obserwacji wynika, że zamortyzowany koszt działania algorytmu wynosi około 2*k, a więc mieści się w
Tablica częściowych dopasowań Celem tej tabeli jest umożliwienie algorytmowi niedopasowywania któregokolwiek znaku z S więcej niż raz. Kluczową obserwacją natury liniowego poszukiwania, która na to pozwala, polega na tym, że mając porównany pewien segment głównego ciągu znaków z początkowym fragmentem wzorca, wiemy dokładnie, w których miejscach mogłoby się zacząć nowe potencjalne dopasowanie przed bieżącą pozycją. Inaczej mówiąc, występuje tutaj „wstępne przeszukiwanie” samego wzorca i zebranie zestawu wszelkich możliwych pozycji do powrotu, które pomijają złe wybory i zwiększają przez to efektywność wyszukiwania wzorca w tekście.
Chcemy mieć możliwość wyszukania, dla każdej pozycji w W, długości najdłuższego możliwego początkowego segmentu W wskazującego (ale nie zawierającego) tę pozycję, inną niż całe segmenty zaczynające się w W, których nie dało się dopasować;