$5) B = a b a a b  => S = 1 0 0 1 0 0 0 0 1; L = 4, R = 5, distanta maxima = 5;$

h3. Solutia 2 (Mircea Pasoi):

h3. Solutia 2 (Mircea Pasoi):
 
Pentru sirul de caractere $S$, determinam pentru fiecare $i$ de la $1$ la $n$ lungimea celui mai lung prefix al lui $S$ cu $S[i..n]$. Aceasta operatie se poate realiza folosind siruri de sufixe. De exemplu, daca $S$ este sirul nostru si $T$ este sirul de potriviri maxime ale sufixelor, atunci:
 
$S = a b b a a b b a a$
$T = 9 0 0 1 5 0 0 1 1$
 
Pentru toate lungimile posibile $k$ ale sablonului $(1 ≤ k ≤ n)$ verificam daca distanta maxima $d$ intre indicii celor mai departate doua elemente de valori mai mari sau egale cu $k$ in sirul $T$ nu este mai mare decat $k$. Prezentam in continuare un exemplu:
 
$k = 9:   9 - - - - - - - -  => d = 9, este bine;$
 
$k = 8;   9 - - - - - - - -  => d = 9, nu este bine;$
 
$k = 7:   9 - - - - - - - -  => d = 9, nu este bine;$
 
$k = 6:   9 - - - - - - - -  => d = 9, nu este bine;$
 
$k = 5:   9 - - - 5 - - - -  => d = 5, este bine;$
 
$k = 4:   9 - - - 5 - - - -  => d = 5, nu este bine;$
 
$k = 3:   9 - - - 5 - - - -  => d = 5, nu este bine;$
 
$k = 2:   9 - - - 5 - - - -  => d = 5, nu este bine;$
 
$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].