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)

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' &le; 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.

Desi exista un algorirm de complexitate $O(n)$ specializat pentru siruri ce contin doar literele $A$ si $B$, metoda preferata de autor (si cu care a obtinut punctaj maxim in timpul concursului) a fost folosirea sirurilor de sufixe, ca in problema anterioara.

h3. *Problema 3*: _substr_ (baraj 2003)

h3. *Problema 3*: _Substr_ (baraj 2003)

Se da un text format din $N$ caractere (litere mari, litere mici si cifre). Un substring al acestui text este o secventa de caractere care apar pe pozitii consecutive in text. Fiind dat un numar $K$, sa se gaseasca lungimea celui mai lung substring care apare in text de cel putin $K$ ori $(1 ≤ N ≤ 16384)$.

Avand sufixele textului sortate, iteram cu o variabila $i$ de la $0$ la $N-K$ si calculam cel mai lung prefix comun intre sufixul $i$ si sufixul $i+K-1$. Prefixul maxim determinat in cursul acestei parcurgeri reprezinta solutia problemei.

h3. *Problema 4*: _ghicit_ (baraj 2003)

h3. *Problema 4*: _Ghicit_ (baraj 2003)

Tu si cu Taranul jucati un joc neinteresant. Tu ai un sir de caractere mare. Taranul iti spune un alt sir de caractere, iar tu trebuie sa raspunzi cat mai repede daca sirul respectiv este sau nu o subsecventa a sirului tau.
Taranul  iti pune multe intrebari si, fiindca esti informatician, te-ai gandit ca ar merge mai repede daca ai sti dinainte toate sirurile despre care te poate intreba.

Aceasta problema ne cere, de fapt, sa calculam numarul de noduri (fara radacina) ale trie-ului de sufixe asociat unui string. Fiecare secventa distincta din sir este determinata de drumul unic pe care il parcurgem in trie-ul de sufixe cand cautam acea secventa. Pentru exemplul $abac$ avem secventele $a$, $ab$, $aba$, $abac$, $ac$, $b$, $ba$, $bac$ si $c$, acestea sunt determinate  de drumul de la radacina trieului spre nodurile $2$, $3$, $4$, $5$, $6$, $7$, $8$ si $9$ in aceasta ordine. Cum constructia trie-ului de sufixe are complexitate patratica, iar construirea unui arbore de sufixe este anevoioasa, este preferabila o abordare prin prisma sirurilor de sufixe. Obtinem sirul sortat de sufixe in $O(n lg n)$, dupa care cautam pozitia in care fiecare pereche de sufixe consecutive difera (folosind functia $lcp$) si adunam la solutie restul caracterelor. Complexitatea totala este $O(n lg n)$.

h3. *Problema 5*: _seti_ (ONI 2002, enunt modificat)

h3. *Problema 5*: _SETI_ (ONI 2002, enunt modificat)

Se da un string de lungime $N$ $(1 ≤ N ≤ 131072)$ si $M$ stringuri de lungime cel mult $64$. Se cere sa se numere aparitiile fiecarui string din cele $M$ in stringul mare.
h3. Solutie:

Se procedeaza ca la siruri de sufixe, numai ca este suficient sa ne oprim dupa pasul 6 unde am calculat relatia de ordine intre stringurile de lungime $2^6^ = 64$. Avand substringurile de lungime 64 sortate, fiecare query este rezolvat cu doua cautari binare. Complexitatea algoritmului este $O(N lg 64 + M * 64 * lg N) = O(N + M lg N)$.

Se procedeaza la fel ca in cazul sirurilor de sufixe, numai ca este suficient sa ne oprim dupa pasul 6, unde am calculat relatia de ordine intre stringurile de lungime $2^6^ = 64$. Avand substringurile de lungime 64 sortate, fiecare query este rezolvat cu doua cautari binare. Complexitatea algoritmului este $O(N lg 64 + M * 64 * lg N) = O(N + M lg N)$.

h3. *Problema 6*: _Subsecventa comuna_ (Olimpiada poloneza si TopCoder 2004, enunt modificat)
 
Se considera trei siruri de caractere $S{~1~}$, $S{~2~}$ si $S{~3~}$, de lungimi $m$, $n$ si $p$ $(1 ≤ m, n, p ≤ 10000)$, sa se determine subsecventa de lungime maxima care este comuna celor trei siruri. De exemplu, daca $S{~1~} = abababca$, $S{~2~} = aababc$ si $S{~3~} = aaababca$, atunci subsecventa comuna de lungime maxima pentru cele trei siruri este $ababc$.
 
h3. Solutie:
 
Daca ar fi vorba doar de doua siruri de lungimi mai mici am putea rezolva usor problema folosind metoda programarii dinamice; astfel, solutia pentru doua siruri ar avea ordinul de complexitate $O(N^2^)$.
O alta idee ar fi sa consideram fiecare sufix al sirului $S{~1~}$ si sa incercam sa ii gasim potrivirea de lungime maxima in celelalte doua siruri.
Potrivirea de lungime maxima rezolvata naiv ar avea complexitatea $O(N^2^)$, dar folosind algoritmul $KMP$ ([8]), putem obtine prefixul maxim al unui sir care se gaseste ca subsecventa in al doilea sir in $O(N)$, iar utilizand aceasta metoda pentru fiecare sufix al lui $S{~1~}$, am avea o solutie al carei ordin de complexitate este $O(N^2^)$.
Sa vedem ce se intampla daca sortam sufixele celor trei siruri:
 
$a§$
$abababca§$
$ababca§$
$abca§$
$bababca§$
$babca§$
$bca§$
$ca§$
$aababc#$
$ababc#$
$abc#$
$babc#$
$bc#$
$c#$
$a@$
$aaababca@$
$aababca@$
$ababca@$
$abca@$
$babca@$
$bca@$
$ca@$
 
Acum interclasam prefixele celor trei siruri (consideram $&sect; < # < @ < a ...)$:
 
$a&sect;$
$a@$
$aaababca@$
$aababc#$
$aababca@$
$abababca&sect;$
$ababc#$
$ababca&sect;$
$ababca@$
$abc#$
$abca&sect;$
$abca@$
$bababca&sect;$
$babc#$
$babca&sect;$
$babca@$
$bc@$
$bca&sect;$
$bca@$
$c@$
$ca&sect;$
$ca@$
 
Subsecventa comuna maxima corespunde prefixelor comune maxime pentru cele trei sufixe $ababca&sect;$, $ababc#$ si $ababca@$. Urmariti unde apar ele in sirul sortat al tuturor sufixelor. De aici avem ideea ca solutia se afla ca o secventa $i..j$ a sirului sortat de sufixe cu proprietatea ca secventa contine cel putin cate un sufix din fiecare sir, iar prefixul cel mai lung comun primului sufix din secventa si ultimul sufix din secventa este maxim; acest cel mai lung prefix este chiar solutia problemei. Alte subsecvente comune ale celor trei siruri ar fi prefixe comune pentru cate o subsecventa a sirului de sufixe sortat, de exemplu $bab$ pentru $bababca&sect;$, $babc@$, $babca&sect;$, sau $a$ pentru $a&sect;$, $a@$, $aaababca@$, $aababc#$. Pentru a determina aceasta secventa de prefix comun maxim putem folosi o parcurgere cu doi indici ({$start$} si $end$). Indicele $start$ variaza intre $1$ si numarul de sufixe, iar $end$ este cel mai mic indice mai mare decat $start$ astfel incat intre $start$ si $end$ sa existe sufixe din toate cele trei siruri. Astfel, perechea $[start, end]$ va indica, la un moment dat, secventa optima $[i..j]$. Aceasta parcurgere este liniara, deoarece $start$ poate avea cel mult $n$ valori, iar $end$ va fi incrementat de cel mult $n$ ori. Pentru a sorta sirul tuturor sufixelor nu este nevoie sa sortam mai intai sufixele fiecarui sir si apoi sa interclasam sufixele. Putem realiza operatia mult mai simplu concatenand cele trei siruri in unul singur (pentru exemplul considerat avem $abababca&sect;aababc@aaababca#)$ si sortand sufixele acestuia.