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]':siruri-de-sufixe#bibliografie si '[10]':siruri-de-sufixe#bibliografie.

h3. *Problema 9* (Olimpiada Baltica de Informatica, 2004)

h3. *Problema 9* (Olimpiada Baltica de Informatica^{%{font-size:12px}'[11]':siruri-de-sufixe#bibliografie%}^, 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.