Diferente pentru suffix-array-liniar intre reviziile #56 si #57

Nu exista diferente intre titluri.

Diferente intre continut:

R' = { 1, 2, 4, 6, 4, 5, 3, 7 }
SR' = {0, 1, 6, 7, 2, 5, 3, 7 }
Pas 2:
h3. Pas 2:
Sortam sufixele de tip 0.
Orice sufix de tip 0 poate fi considerat ca o pereche (caracter, sufix de tip 1): S0,i = Ci + S1,i+1
Se poate folosi radix sort pentru a sorta aceste perechi.
Pas 3:
h3. Pas 3:
Interclasam cei doi vectori sortati de sufixe. Avem doua cazuri la comparare. Acestea pot fi reduse la compararea sufixelor de tip 1 cu sufixe de tip 2 astfel:
1. sufix de tip 0 (Si) cu sufix de tip 1 (Sj) -> (caracter, sufix de tip 1) - (caracter, sufix de tip 2) : (Ci + S1,i+1) - (Cj + S2,j+1)
2. sufix de tip 0 (Si) cu sufix de tip 2 (Sj) -> (caracter, caracter, sufix de tip 2) - (caracter, caracter, sufix de tip 1) : (Ci + Ci+1 + S2,i+2) - (Cj + Cj+1 + S1,j+2)
# sufix de tip 0 (Si) cu sufix de tip 1 (Sj) -> (caracter, sufix de tip 1) - (caracter, sufix de tip 2) : (Ci + S1,i+1) - (Cj + S2,j+1)
# sufix de tip 0 (Si) cu sufix de tip 2 (Sj) -> (caracter, caracter, sufix de tip 2) - (caracter, caracter, sufix de tip 1) : (Ci + Ci+1 + S2,i+2) - (Cj + Cj+1 + S1,j+2)
Analiza complexitatii:
h2. Analiza complexitatii:
Se observa ca fiecare pas poate fi efectuat in timp liniar.
Algoritmul se repeta pe un sir de lungime 2N / 3. De aici complexitatea poate fi data de recurenta T(N) = T(2N / 3) + O(N) => T(N) = O(N).

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.