h3. Solutie:

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

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_':http://infoarena.ro/problema/seti (ONI 2002, enunt modificat)

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@$

p=. !siruri-de-sufixe?fig08.png!

Acum interclasam prefixele celor trei siruri (consideram $&sect; < # < @ < a ...)$:

$a§$
$a@$
$aaababca@$
$aababc#$
$aababca@$
$abababca§$
$ababc#$
$ababca§$
$ababca@$
$abc#$
$abca§$
$abca@$
$bababca§$
$babc#$
$babca§$
$babca@$
$bc@$
$bca§$
$bca@$
$c@$
$ca§$
$ca@$

p=. !siruri-de-sufixe?fig09.png!

Subsecventa comuna maxima corespunde prefixelor comune maxime pentru cele trei sufixe $ababca§$, $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§$, $babc@$, $babca§$, sau $a$ pentru $a§$, $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§aababc@aaababca#)$ si sortand sufixele acestuia.

$7: baab$
$8: baabaab$

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

p=. !siruri-de-sufixe?fig12.png!

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$

p=. !siruri-de-sufixe?fig10.png!

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;$

p=. !siruri-de-sufixe?fig11v.png!

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].