Clasele 11-12 lecția 15 - 14 ian 2015

From Algopedia
Revision as of 21:32, 13 January 2015 by Cata (talk | contribs) (→‎Construcție în O(n log n))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Rotația lexicografic minimă

Problemă rămasă de ultima dată: cum modificăm algoritmul KMP pentru a afla rotația lexicografic minimă a unui șir? Ora trecută am găsit doar un algoritm bazat pe arbori de sufixe, care este greu de implementat în O(n).

Șiruri de sufixe

Am văzut în ultima lecție că arborii de sufixe sunt o structură utilă în multe probleme cu șiruri de caractere. Arborii de sufixe se pot construi în O(n) cu un algoritm greoi. Algoritmul mai simplu necesită timp O(n2) și memorie O(n).

Șirurile de sufixe oferă răspunsuri la aceleași tipuri de întrebări ca și arborii de sufixe, dar sunt mai ușor de implementat. Construcția lor în O(n) este încă greoaie, dar o construcție în O(n log n) este mult mai la îndemână.

Definiție

Un șir de sufixe este un șir ordonat al tuturor sufixelor unui șir. De exemplu, pentru S = "abracadabra", șirul de sufixe este

A = { "a", "abra", "abracadabra", "acadabra", "adabra", "bra", "bracadabra", "cadabra", "dabra", "ra", "racadabra" }

În practică, nu avem nevoie să stocăm explicit sufixele, căci aceasta necesită memorie O(n2). Întrucât știm că sunt sufixe, avem nevoie să stocăm doar poziția de început în S:

A = { 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2 }

Construcție în O(n log n)

Metoda folosită se numește dublarea prefixului. Pornim cu ordinea caracterelor individuale din șir. Din ea, calculăm ordinea prefixelor de lungime 2 ale fiecărui sufix, apoi a celor de lungime 4 etc. Avem nevoie de log n iterații, iar fiecare iterație poate fi completată în O(n).

subșir număr de ordine
a 0
b 1
r 17
a 0
c 2
a 0
d 3
a 0
b 1
r 17
a 0
subșir număr de ordine
ab 1
br 5
ra 10
ac 3
ca 7
ad 4
da 8
ab 1
br 5
ra 10
a$ 0
subșir număr de ordine
abra 1
brac 6
raca 10
acad 3
cada 7
adab 4
dabr 8
abra 1
bra$ 5
ra$$ 9
a$$$ 0
subșir număr de ordine
abracada 2
bracadab 6
racadabr 10
acadabra 3
cadabra$ 7
adabra$$ 4
dabra$$$ 8
abra$$$$ 1
bra$$$$$ 5
ra$$$$$$ 9
a$$$$$$$ 0

Observații:

  • Pentru construcția rapidă, nu este necesar să sortăm caracterele prima oară. Putem să le atribuim valorile P[0][i] = S[i] - 'a'
  • La fiecare pas intermediar, sortăm practic perechi de numere de ordine, prin metoda radix sort. De exemplu, la pasul 3, brac și bra$ corespund perechilor (5, 3) și respectiv (5, 0), deci bra$ va primi un număr de ordine strict mai mic decât brac.
  • Dacă două substringuri sunt egale, este important ca ele să capete același număr de ordine.
  • Matricea intermediară de dimensiuni log n x n poate sau nu să fie necesară, în funcție de natura problemei.
  • La sfârșitul construcției, vectorul de pe ultima linie a matricei este indirectarea vectorului de sufixe. Pozițiile elementelor 0, 1, ..., n-1 în acel șir dau vectorul de sufixe
    • Exemplu: pentru "abracadabra", ultima linie a matricei este { 2, 6, 10, 3, 7, 4, 8, 1, 5, 9, 0 }.
  • La fiecare pas, informația despre prefixe de lungime 2k trebuie sortată. Articolul infoarena spune că sort() se comportă mai bine decât radix sort. Experimentele mele arată contrariul - radix sort merge de 2-3 ori mai repede pentru N = 100.000.

Matricea finală rezultată este:

k 2k a b r a c a d a b r a $ $ $ $ $ $ $
0 1 0 1 17 0 2 0 3 0 1 17 0
1 2 1 5 10 3 7 4 8 1 5 10 0
2 4 1 6 10 3 7 4 8 1 5 9 0
3 8 2 6 10 3 7 4 8 1 5 9 0

Construcție în O(n), metoda recursivă

Vezi articolul de la infoarena și o prezentare.

(exemplu pentru "abracadabra")

Complexitatea este T(n) = T(2n/3) + n, așadar T(n) = O(n).

Observații:

  • de ce alegem grupe de 3 caractere și nu de două?

Cele mai lungi prefixe comune

În general, ne ajută dacă putem răspunde la întrebări de forma „care este cel mai lung prefix comun între sufixul care începe la poziția i și sufixul care începe la poziția j?” Vom nota răspunsul la această întrebare cu LCP(i, j).

LCP(i, j) poate fi calculat în timp O(log n) din matricea P. La fiecare pas k, dacă P[k][i] = P[k][j], atunci prefixul comun are lungime cel puțin 2k, la care adăugăm LCP(i + 2k, j + 2k). Dacă P[k][i] ≠ P[k][j], atunci ne întrebăm dacă prefixul comun are lungime cel puțin 2k-1. În orice caz, trecem la pasul k - 1.

Dacă dorim să reducem timpul la O(1), trebuie să calculăm și să stocăm L[i] = LCP(i -1, i) pentru fiecare i. Apoi, LCP(i, j) = min(L[i + 1], L[i + 2], ..., L[j]). Calculăm acest minim în O(1) cu RMQ (greu de implementat în timp de concurs).

Cum calculăm vectorul L? Algoritmul este simplu și rulează în O(n) odată ce avem vectorul A și inversul său A-1, dar pornește de la o propoziție neintuitivă.

Să examinăm din nou șirul de sufixe pentru stringul "abracadabra":

A = { "a", "abra", "abracadabra", "acadabra", "adabra", "bra", "bracadabra", "cadabra", "dabra", "ra", "racadabra" }

sau, numeric,

A = { 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2 }

Fie A-1 vectorul invers al lui A (sau, echivalent, ultima linie din matricea P). Așadar, A-1 indică, pentru fiecare sufix S[i...n-1], poziția lui în A:

A-1 = { 2, 6, 10, 3, 7, 4, 8, 1, 5, 9, 0 }

vectorul L rezultat (cel mai lung prefix comun între fiecare sufix și predecesorul lui) va fi:

L = { 0, 1, 4, 1, 1, 0, 3, 0, 0, 0, 2 }

Propoziție: pentru orice i > 0, L[A-1[i + 1]] ≥ L[A-1[i]] - 1

Demonstrație: Pentru sufixul S[i...n-1], să considerăm sufixul imediat anterior lexicografic, S[j...n-1]. Fie l = L[A-1[i]] = LCP(i, j). Dacă l = 0, atunci propoziția este evident adevărată. Dacă l > 0, atunci S[j] = S[i], S[j+1...n-1] < S[i+1...n-1] și LCP(i + 1, j + 1) = l - 1.

Acum, fie S[k...n-1] sufixul imediat anterior lexicografic al lui S[i+1...n-1]. Atunci ori k = j + 1, ori S[j+1...n-1] < S[k...n-1] < S[i+1...n-1]. De aceea,

L[A-1[i + 1]] = LCP(i+1, k) ≥ LCP(i + 1, j + 1) = l - 1.

Exemplu: Fie i = 2. Atunci:

  • S[2...10] = "racadabra"
  • A-1[2] = 10 ("racadabra" este al 10-lea sufix lexicografic, ultimul)
  • j = 9 (S[9...10] = "ra" este sufixul lexicografic anterior lui "racadabra")
  • l = L[A-1[2]] = L[10] = 2 ("racadabra" are două litere în comun cu sufixul anterior, "ra")
  • trebuie să verificăm că L[A-1[3]] ≥ 1, cu alte cuvinte că "acadabra" are cel puțin o literă în comun cu prefixul anterior lexicografic
  • S[2] = S[9] = "r"
  • S[10...10] < S[3...10] ("a" < "acadabra" prin eliminarea lui "r")
  • LCP("a", "acadabra") = l - 1 = 1
  • k = 0 ("abracadabra" este sufixul lexicografic anterior lui S[i+1...n-1])
  • deci avem ordinea S[10...10] < S[0...10] < S[3...10] ("a" < "abracadabra" < "acadabra")
  • de aceea, L[A-1[3]] = LCP("abracadabra", "acadabra") ≥ LCP("a", "acadabra") = 1

Pseudocodul este:

l = 0;
for (i = 0; i < n; i++) {       // exemplu: i = 0
  k = A<sup>-1</sup>[i];        // k = 2, însemnând că sufixul S[i..10] = "abracadabra" are numărul de ordine 2
  j = A[k  1];                 // j = A[1] = 7, însemnând că S[j..10] = "abda" este sufixul anterior lui "abracadabra"
  while (S[i + l] == S[j + l]) {
    l = l + 1;
  }                             // căutăm naiv cel mai lung prefix comun; vom găsi l = 4
  L[k] = l;                     // salvăm această valoare în L
  if (l > 0) {
    l = l - 1;                  // pregătim l = 3, căci următorul sufix, "bracadabra" are cel puțin trei litere în comun cu "bra", conform propoziției
  }

Aplicații

Vom căuta soluții pentru aceste aplicații atât cu arbori de sufixe, cât și cu șiruri de sufixe.

Căutare de subșir în șir

Se face printr-o căutare binară în A. Observăm că arborele de sufixe funcționează într-o manieră complementară algoritmului KMP. Acesta din urmă preprocesează subșirul, apoi poate căuta rapid oricâte șiruri. Vectorul de sufixe necesită o preprocesare a șirului, după care poate căuta rapid oricâte subșiruri.

Numărul de apariții ale unui subșir în șir

Se face prin două căutări binare. Pentru găsirea subșirului "abc", trebuie să găsim prima și ultima apariție a lui "abc" ca prefix în șirul de sufixe. Putem face aceasta cu două căutări binare care diferă ușor. Mai simplu, putem folosi o singură rutină pentru a căuta șirurile "abc" și "abd".

Costul fiecărei căutări binare, dacă o implementăm naiv, este O(|P| log n), unde P este subșirul căutat. Ea poate fi redusă la O(|P| + log n) dacă putem răspunde la LCP(i, j) în timp O(1) (vezi mai jos). Iată o explicație digerabilă.

Rotația minimă dpdv lexicografic

Se rezolvă prin concatenarea șirului cu el însuși și construirea șirului de sufixe pentru șirul de lungime 2n.

Cel mai lung subșir care apare de cel puțin K ori

După calculul șirului de sufixe și al celor mai lungi prefixe între fiecare două prefixe consecutive, calculăm minimul din LCP pentru fiecare subsecvență de K elemente.

(Discuție: Soluția lui Mihai Pătrașcu, cu tabele hash).

Al k-lea sufix în ordine lexicografică

Banal, este A[k].

Numărul de subsecvențe distincte ale unui șir

Vezi problema Ghicit de la Infoarena.

Să ne închipuim subsecvențele grupate după poziția de început. Există n subsecvențe care încep la poziția 0, n - 1 subsecvențe care încep la poziția 1 etc. Acum, să examinăm aceste poziții de început în ordinea lexicografică a perechilor. Pentru poziția A[i], am contabilizat deja o parte din perechi. Câte? Numărul lor este dat de lungimea celui mai lung prefix comun între sufixele (i-1) și i.

De exemplu, pentru șirul "xabyabz", A = { abyabz, abz, byabz, bz, xabyabz, yabz, z }.

Câte subsecvențe noi încep la primul "a"? Momentan toate 6: "a", "ab", "aby", "abya", "abyab", "abyabz".

Câte subsecvențe noi încep la cel de-al doilea "a"? Doar una: "abz", deoarece pe "a" și pe "ab" le-am contabilizat la pasul anterior.

Deci la fiecare pas i adăugăm la răspuns valoarea n - A[i] - LCP[i, i-1], unde A[i] este șirul (numeric) de sufixe ordonate.

Temă