Informatyka MIMUW

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.