Drzewa sufiksowe - przez tablice sufiksowe


sigma = {1, ..., n}

T = t0 t1 t(n-1) 0 0 0 0 0 (wypełniamy zerami)
S_i = sufiks t(i) ... t(n-1)
S_n = epsilon

chcemy leksykograficznie uporządkować wszystkie sufiksy. oczywiście nie
chcemy przechowywac wszystkich sufiksow, lecz chcemy tylko permutacje
indeksow

SA[0..n] of 0..n

SA - permutacja liczb 0..n taka, że S(SA[i]) < S(SA[i+1])

chcemy to zrobić w O(n)

redukujemy zadanie rozm n -> 2/3*n

przykład

                    111
          0123456789012
niech T = yabbadabbado

     0  1  2  3  4  5  6  7  8  9 10 11 12
SA= 12  1  6  4  9  3  8  2  7  5 10 11  0

koniec przykladu

Krok 0 - konstrukcja próbki

B(k) == def == {i \in 0..n: i mod 3 = k}
k=0,1,2

C = B(1) + B(2)

S(C) = {S_i: i \in C} - próbki

Krok 1 - sortujemy leksykograficznie próbki, ale sprytnie

k = 1,2
budujemy słowo R_k = [t_k, t_k+1, t_k+2][t_k+3, t_k+4, t_k+5]...
[xyz] - pojedynczy symbol
R = R1 concat R2

R = [abb][ada][bba][do0][bba][dab][bad][o00]
     S1   S4   S7   S10  S2   S5   S8   S11

ta odpowiedniość zachowuje porządek leksykograficzny (m.in. dzięki temu,
że wypełnialiśmy zerami, które są najmniejsze)

oczywiście nie używamy w rekurencyjnym wywołaniu tych dzikich trójek, tylko
sortujemy je leksykograficznie między sobą i nadajemy im nowe cyferki, więc
nasze R tak naprawdę to jest

R'=(  1,  2,  4,  6,  4,  5,  3,  7)
     S1  S4  S7 S10  S2  S5  S8 S11

Teraz dopiero rekurencyjne znajdujemy tablicę sufiksową dla R', mamy więc
porządek między nimi.

SA' = (epsilon, S1, S4, S8, S2, S7, S5, S10, S11)

wszystko liniowo póki co

pozostają sufiksy z pozycji podzielnych przez 3

niech S_i, S_j in B_0. ale wtedy

S_i <= S_j <==> (t_i, S_i+1) <= (t_j, S_j+1) !

yuppi!

mamy sortowanie leksykograficzne nad alfabetem rozmiaru n, więc możemy
posortować w O(n) sufiksy z B_0.

teraz trzeba to zmergować. i trzeba nam umieć porównywać elementy z B_0
z elementami B_1+B_2

niech S_i in B_0, S_j in B_1+B_2. chcemy porównywać

(1) S_j in B_1: prosto: S_i = t_i S_i+1, S_j = t_j S_j+1, ale S_i+1 umiemy
    porównać z S_j+1 (bo S_j+i in B_2)

(2) S_j in B_2: podobnie: ale bierzemy 2 symbole do porównywania ręcznego:
    S_i = t_i t_i+1 S_i+2, S_j = t_j t_j+1 S_j+2, ale S_i+2 oraz S_j+2
    możemy porównać.

koniec.