Mai intai trebuie sa te autentifici.
Diferente pentru siruri-de-sufixe intre reviziile #15 si #16
Nu exista diferente intre titluri.
Diferente intre continut:
De obicei, in probleme unde apare rotatia unui sir dat, putem sa ne folosim de trucul de a concatena sirului de caractere acelasi sir pentru a simplifica problema. Dupa aceasta transformare problema ne cere subsecventa lexicografica minima de lungime n a noului sir. Ordinea subsecventelor de lungime n ale unui sir este egala cu ordinea sufixelor determinate de subsecventele date, deci ne putem folosi de arborii de sufixe pentru a rezolva aceasta problema. O problema asemanatoare a fost propusa de unul dintre autori la concursul Bursele Agora, editia 2003-2004, care se putea rezolva pe aceiasi idee. Implementarea trebuia facuta atent pentru solutia oficiala era o rezolvare eficienta ce nu folosea aceasta structura de date.
h3. *Problema 2*: _sir_ (baraj 2004)
Se considera un sir $c{~1~}c{~2~}...c{~n~}$ format din $n$ $(1 ≤ n ≤ 30 000)$ caractere din multimea ${A, B}$. Concatenam sirul cu el insusi si obtinem un sir de lungime $2n$. Pentru un indice $k$ $(1 ≤ k ≤ 2n)$ consideram subsecventele de lungime cel mult $n$, care se termina pe pozitia $k$, iar dintre acestea fie $s(k)$ subsecventa cea mai mica in ordine lexicografica. Determinati indicele $k$ pentru care $s(k)$ are lungimea cea mai mare.
_Nota suplimentara_: fie $X$ si $Y$ doua siruri oarecare, iar $o$ operatia de concatenare. In aceasta problema se va considera ca $X > X o Y$.
h3. Solutie:
Sirul cautat este prima permutare circulara in ordine lexicografica a sirului dat. Notam cu $S{~i~}^k^$ substringul de lungime $k$ ce incepe la pozitia $i$. Fie $S{~i~}^n^$ cel mai mic substring in ordine lexicografica de lungime $n$ al sirului obtinut prin concatenare. Presupunand prin absurd ca $s(i+n-1) < n$ ar insemna ca exista un $i'$ $(i < i' ≤ j)$ astfel incat $S{~i'~}^j-i'+1^$ este lexicografic mai mic decat $S{~i~}^n^$. Dar din conditia impusa de enunt avem $S{~i'~}^j-i'+1^ > S{~i'~}^n^$. Dar $S{~i'~}^n^ > S{~i~}^n^$ => contradictie.
Desi exista un algorirm de complexitate $O(n)$ pentru aceasta, metoda preferata de autor (si cu care a obtinut punctaj maxim in timpul concursului) a fost folosirea sirurilor de sufixe, ca in problema anterioara.
