$*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)$.

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)$.
 
h3. *Problema 10* (ACM SEER 2004)
 
Avand un sir de caractere $S$ dat, se cere ca pentru fiecare prefix al sau sa se determine daca este un sir de caractere periodic. Astfel, pentru fiecare $i$ $(2 ≤ i ≤ N)$ ne intereseaza cel mai mare $K > 1$ (daca exista un asemenea $K$) cu proprietatea ca prefixul lui $S$ de lungime $i$ poate fi scris cub forma $A^k^$ (sirul $A$ concatenat cu el insusi de $k$ ori) pentru un sir de caractere $A$. De asemenea, ne intereseaza si valoarea $k$ (avem $0 ≤ N ≤ 1000000$).
 
h4. Exemplu
 
Pentru sirul $aabaabaabaab$ obtinem rezultatul prezentat in continuare:
 
$2 2$
$6 2$
$9 3$
$12 4$
 
h4. Explicatii
 
* prefixul $aa$ are perioada $a$;
* prefixul $aabaab$ are perioada $aab$;
* prefixul $aabaabaab$ are perioada $aab$;
* prefixul $aabaabaabaab$ are perioada $aab$;
 
h3. Solutie:
 
Sa vedem ce se intampla cand incercam sa potrivim un sir cu un sufix al sau. Consideram un sir si il impartim in doua, obtinand un prefix si un sufix:
 
$S = aab aabaabaaaab$
$suf = aab aabaaaab$
$pre = aab$
 
Daca sufixul se potriveste cu sirul initial pe un numar de caractere mai mare sau egal cu lungimea sirului $pre$, inseamna ca $pre$ este si un prefix al sufixului; deducem ca putem imparti si sufixul in $pre$ si $suf1$, iar sirul putem sa il impartim in $pre$, $pre$ si $suf1$. Daca sirul se potriveste cu sufixul pe un numar de caractere mai mare sau egal cu dublul lungimii sirului $pre$, atunci sufixul se potriveste cu $suf1$ pe un numar de caractere mai mare sau egal cu lungimea sirului $pre$, deci $suf1$ poate fi scris ca $pre$ si $suf2$, deci $suf$ poate fi scris ca $pre$, $pre$, $suf2$, iar $S$ poate fi scris ca $pre$, $pre$, $pre$, $suf2$:
 
$S = aab aab aab aaaab$
$suf = aab aab aaaab$
$suf1 = aab aaaab$
$pre = aab$
 
Observam astfel ca daca sirul $S$ se potriveste cu sufixul sau pe cel putin $k * |pre|$ caractere, atunci $S$ are un prefix de lungime $(k+1) * |pre|$ care este periodic. Folosindu-ne de structura de date $siruri de sufixe$, putem determina pentru fiecare sufix potrivirea maxima cu sirul initial. Daca al $i$-lea sufix se potiveste cu sirul pe primele $k * (i-1)$ pozitii, atunci putem actualiza informatia care indica daca prefixele de dimensiune $j * (i-1)$ (unde $2 ≤ j ≤ k$) sunt periodice. Pentru fiecare sufix $S$, actualizarea tuturor informatiilor are ordinul de complexitate $O(n / (i-1))$. Astfel, ordinul de complexitate al algoritmului de rezolvare a acestei probleme este $O(n log n)$. Trebuie remarcat faptul ca putem obtine o rezolvare in timp $O(n)$ folosind o idee similara si algoritmul $KMP$, dar prezentarea acestei rezolvari depaseste scopul acestui articol.