Przedstawimy jeden z możliwych algorytmów liniowych obliczania tablicy P. Jest to iteracyjna wersja algorytmu rekurencyjnego, który moglibyśmy otrzymać korzystając z faktu:
Jeśli x[j]=x[t+1] oraz t=P[j−1], to P[j]=t+1
W algorytmie obliczania P[j] korzystamy z wartości P[k], dla k<j.
Algorytm Prefikso-Sufiksy
P[0]:=-1; t:=-1; for j:=1 to m do begin while t=> 0 and x[t+1] <> x[j] do t:=P[t]; t:=t+1; P[j]:=t; end;
Złożoność liniowa wynika stąd, że w każdej iteracji zwiększamy wartość t co najwyżej o jeden, a wykonanie każdej operacji t:=P[t] zmniejsza wartość t co najmniej o jeden. Proste zastosowanie zasady magazynu (lub potencjału) implikuje, że operacji t:=P[t] wykonujemy co najwyżej n. Dowód poprawności pozostawiamy jako ćwiczenie.