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.