Informatyka MIMUW

Pokażemy pewne proste zastosowanie tablic prefikso-sufiksów. Słowem pokrywającym tekst x jest każdy taki tekst y, którego wystąpienia w x pokrywają cały tekst x. Na przykład słowo y=aba pokrywa tekst x=ababaaba, natomiast nie pokrywa tekstu abaaababa. Zajmiemy się problemem: obliczyć w czasie liniowym długość najkrótszego słowa pokrywającego dany tekst x.

Niech \( S[i] \) będzie rozmiarem minimalnego słowa pokrywającego tekst \( x[1..i] \).

Następujący algorytm oblicza długość minimalnego słowa pokrywającego tekstu x. Algorytm jest efektywny ponieważ liczy dodatkową tablicę Zakres. W \( i \)-tej iteracji algorytmu pamiętany jest znany dotychczas zakres każdego minimalnego słowa pokrywającego.

Rysunek 1: \( i \)-ta iteracja algorytmu dla \( i=15 \) oraz słowa \( x\ =\ abaabababaababa\ldots \). Tuż przed rozpoczęciem tej iteracji mamy \( P[i]=8 \), \( S[8]=2,\ Zakres[3]=13 \). Zatem spełniony jest warunek \( i-Zakres[S[P[i]] \le S[P[i]] \). Po zakończeniu \( i \)-tej iteracji mamy \( S[15]=3,Zakres[3]=15 \).

Algorytm Rozmiar-Minimalnego-Pokrycia

for i:=2 to n do begin
    Zakres [i]=i; S [i]=i;
end;
for i:=2 to n  do
    if P [i]>0 and i-Zakres[S[P[i]]] <= S[P[i]] then begin
      S[i] :=S[P[i]]; Zakres[S[P[i]] :=i
    end;
return S[n];