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.