Obliczanie Tablicy Silnych Prefikso-Sufiksów

Algorytm liczenia silnych prefikso-sufiksów bazuje na następującej relacji między P a P':

\( (t=P[j]\ \textrm{oraz}\ x[t+1]\neq x[j+1])\ \Rightarrow\ P'[j]=t \)

\( (t=P[j],\ t\ge 0,\ \textrm{oraz}\ x[t+1]= x[j+1])\ \Rightarrow\ P'[j]=P'[t] \)

Nie musimy obliczać tablicy P; potrzebna jest jedynie ostatnia wartość \( t=P[j] \), którą obliczamy on-line.

Algorytm Silne-Prefikso-Sufiksy

P'[0]:=-1; t:=-1; 
for j:= 1 to m do 
  while t => 0 and x[t+1] <> x[j] do 
    t:=P'[t]; 
  t:=t+1; 
  if j=m or x[t+1] <> x[j+1] 
    then P'[j]:=t else P'[j]:=P'[t];

Gdy weźmiemy \( x\ =\ aba^{m-2} \) to
\( P'[0]=-1 \), \( P'[1]=0 \), \( P'[2]=-1 \), oraz dla \( 3\leq j\leq m \) \( P'[j]=1 \).
Jest to jest pesymistyczny przypadek dla algorytmu Silne-Prefikso-Sufiksy, algorytm wykonuje wtedy \( 3m-5 \) porównań symboli.

Informatyka MIMUW

Obliczanie Tablicy Silnych Prefikso-Sufiksów