$k = 1:   9 - - 1 5 - - 1 1  => d = 3, nu este bine;$

Cea mai mica valoare a lui $k$ pentru care distanta $d$ este suficient de mica reprezinta lungimea sablonului cautat (in cazul precedent $k = 5$). Pentru a obtine un algoritm de complexitate buna trebuie ca acest pas sa fie eficient; putem sa folosim un arbore de intervale, sa folosim un contor cu $k$ care variaza de la $1$ la $n$ si sa eliminam din arbore elemente de marime mai mica decat $k$ si, la fiecare pas, sa actualizam arborele pentru a putea raspunde la interogari de genul: _care este distanta maxima intre doua elemente care exista acum in structura_. Algoritmul are complexitatea $O(N log N)$. Pentru o prezentare amanuntita a arborilor de intervale, va recomand [9] si [10].

Cea mai mica valoare a lui $k$ pentru care distanta $d$ este suficient de mica reprezinta lungimea sablonului cautat (in cazul precedent $k = 5$). Pentru a obtine un algoritm de complexitate buna trebuie ca acest pas sa fie eficient; putem sa folosim un arbore de intervale, sa folosim un contor cu $k$ care variaza de la $1$ la $n$ si sa eliminam din arbore elemente de marime mai mica decat $k$ si, la fiecare pas, sa actualizam arborele pentru a putea raspunde la interogari de genul: _care este distanta maxima intre doua elemente care exista acum in structura_. Algoritmul are complexitatea $O(N log N)$. Pentru o prezentare amanuntita a arborilor de intervale, va recomand $[9]$ si $[10]$.
 
h3. *Problema 9* (Olimpiada Baltica de Informatica, 2004)
 
Un sir de caractere $S$ se numeste repetitie $(K, L)$ daca $S$ se obtine prin concatenarea de $K ≥ 1$ ori a unui sir $T$ de lungime $L ≥ 1$. De exemplu, sirul $S = abaabaabaaba$ este o repetitie $(4, 3)$ cu $T = aba$. Sirul $T$ are lungimea trei si $S$ se obtine repetandu-l pe $T$ de patru ori. Avand un sir de caractere $U$ format din caractere $a$ si/sau $b$ de lungime $n$ $(1 ≤ n ≤ 50000)$, va trebui sa determinati o repetitie $(K, L)$ care apare ca subsecventa a lui $U$ astfel incat $K$ sa fie cat mai mare. De exemplu, sirul $U = babbabaabaabaabab$ contine repetitia $(4, 3)$, sirul $S$ incepand de pe pozitia $5$. Aceasta este si repetitia maxima, deoarece sirul nu mai contine nici o alta subsecventa care sa se repete de mai mult de patru ori. Daca sirul contine mai multe solutii cu acelasi $K$, poate fi aleasa oricare dintre ele.
 
h3. Solutie:
 
Dorim ca pentru un $L$ fixat sa determinam cea mai mare valoare $K$ astfel incat in sirul $U$ sa avem o subsecventa $S$ care este repetitie $(K, L)$. Vom considera acum un exemplu: $U = babbabaabaabaabab$, $L = 3$ si o subsecventa fixata $X = aab$ care incepe pe pozitia $4$ a sirului $U$. Putem incerca sa extindem secventa $aab$ la ambele capete cat mai mult posibil prin repetarea ei asa cum vedem in continuare:
 
$b a b *a a b* a a b a a b a a a b$
$*a* a b a a b$
$ a b a a b a a b a a b a *a b a*$
 
Extinzand in acest mod cat mai mult in stanga secventa noastra si apoi extinzand la dreapta prefixul de lungime $L$ (in exemplul nostru prefixul de lungime $3$) al secventei obtinute, gasim cea mai lunga repetitie a unui sir de caractere de lungime $L$ cu proprietatea ca repetitia contine ca subsecventa sirul $X$ (daca repetitia este $(1, L)$ afirmatia anterioara nu este adevarata, dar acesta este un caz trivial). Acum observam ca pentru a identifica toate repetitiile $(K, L)$ cu $L$ fixat din sirul $U$, este suficient sa partitionam sirul in $n/L$ bucati si sa extindem aceste bucati. Remarcam ca daca va fi posibil sa realizam acest lucru pentru ficare bucata in $O(1)$ algoritmul final va avea ordinul de complexitate $O(n/1 + n/2 + n/3 + .. + n/n)$ (fiecare bucata se poate repeta in totalitate sau doar partial in stanga sau in dreapta, iar noi nu vom extinde fiecare bucata separat, ci bucatile adiacente le vom reuni intr-o noua bucata; asadar, daca avem $p$ bucati consecutine de aceeasi dimensiune, vom determina extinderile lor maxime in timp $O(p)$). Dar stim ca sirul $1 + 1/2 + 1/3 + 1/4 + .. + 1/n - ln n$ converge spre o constanta $c$, numita constanta lui $Euler$, si $c < 1$; de aici tragem concluzia ca $O(n/1 + n/2 + n/3 + .. + n/n)$ = $O(log n)$, deci algoritmul, in cazul in care extinderile maxime pot fi calculate usor, ar avea ordinul de complexitate $O(n log n)$. Acum intervin in rezolvarea noastra arborii de sufixe. Pentru a determina cu cat putem extinde cel mai mult subsecventa $U[i..j]$ a sirului $U$ la dreapta, practic ne intereseaza cel mai lung prefix comun al subsecventei $U[i..j]$ si al subsecventei $U[j+1..n]$. Pentru a extinde cat mai mult la stanga este suficient sa inversam sirul $U$ si ajungem sa rezolvam aceeasi problema. Am vazut ca problema celui mai lung prefix comun a doua secvente se rezolva in timp $O(1)$ cu ajutorul sirurilor de sufixe. Astfel, avem nevoie de crearea sirului de sufixe, etapa pe care o rezolvam intr-un timp de ordinul $O(n log n)$ si apoi de aplicarea algoritmului explicat anterior care are complexitatea $O(n log n)$. In concluzie, algoritmul prezent are complexitatea totala $O(n log n)$.