Obliczanie tablicy Prefikso-Sufiksów

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.