Informatyka MIMUW

Niech $rank(i)$ będzie pozycją $sufiks_i$ w porządku leksykograficznym. W naszym przykładowym słowie mamy:

$rank\ =\ [8,\ 2,\ 7,\ 1,\ 3,\ 9,\ 4,\ 10,\ 5,\ 12,\ 1,\ 6]$

Niech $lcp'[k]\ =\ lcp[rank[k]-1]$.

Załóżmy, dla uproszczenia, że $lcp[0]=0$ oraz że tekst kończy się specjalnym symbolem Obliczamy tablice $lcp',\ lcp$ następująco:

Algorytm Oblicz-lcp

for k:=1 to n do 
  oblicz lcp'[k] korzystając z faktu, że lcp'[k] => lcp'[k-1]-1; 
  // koszt iteracji O(lcp'[k]-lcp'[k-1]+const)  
for k:=1 to n do 
  lcp[rank[k]-1] := lcp'[k] \)

Można to zapisać w języku C++ następująco

Algorytm Oblicz-lcp1

for (int i=1; i < =n; i++) R[SUF[i]] = i; 
l = 0;  
for (int i=1; i < =n; i++) 
if (R[i] >; 1) { 
while (x[l+i] == x[l+SUF[R[i]-1]]); 
lcp[R[i]-1] = l;} 
l = max(0, l-1);}

Pozostawiamy jako ćwiczenie dowód tego, że

$lcp'[k]\ge lcp'[k-1]-1$.

Jeśli $lcp'[k-1]-1=t$, to $lcp'[k]$ obliczamy sprawdzając symbol po symbolu (od lewej do prawej) zgodność prefiksów odpowiednich słów startując od pozycji $t$. W ten sposób sumaryczny koszt jest liniowy. W każdej iteracji cofamy się o jeden, a potem idziemy do przodu (sprawdzając kolejne symbole). Jest to analiza typu jeden krok do tyłu i kilka do przodu. Liczba iteracji jest liniowa, więc liczba kroków do tyłu też. Ponieważ odległość do celu jest liniowa, to suma kroków też jest liniowa.