Daca ar fi vorba doar de doua siruri de lungimi mai mici am putea rezolva usor problema folosind metoda programarii dinamice; astfel, solutia pentru doua siruri ar avea ordinul de complexitate $O(N^2^)$.
O alta idee ar fi sa consideram fiecare sufix al sirului $S{~1~}$ si sa incercam sa ii gasim potrivirea de lungime maxima in celelalte doua siruri.

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

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

$ca§$
$ca@$

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.

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.

h3. *Problema 7*: _Cel mai lung palindrom_ (USACO Training Gate)

h3. Solutie:

Daca dorim sa determinam, pentru un indice fixat $i$, care este cel mai mare palindrom centrat in $i$ atunci ne intereseaza prefixul maxim al subsecventei $S[i+1..n]$ care se potriveste cu prefixul subsecventei $S[1..i]$ reflectate. Pentru a rezolva cu usurinta aceasta problema sortam impreuna si sufixele sirului cu prefixele reflectate ale sirului (operatie care se realizeaza usor concatenand sirul $S§$ cu sirul $S$ oglindit $S^'^$) si vom efectua interogari pentru cel mai lung prefix comun pentru $S[i+1]$ si $S^'^[n-i+1]$ $(S^'^[n-i+1] = S[1..i])$, la care putem raspunde folosind siruri de sufixe in timp $O(1)$. Astfel, putem rezolva problema in timp $O(N log N)$. Sa observam ca am tratat aici doar cazul in care palindromul este de lungime para, dar cazul in care palindromul are lungime impara se trateaza analog.

Daca dorim sa determinam, pentru un indice fixat $i$, care este cel mai mare palindrom centrat in $i$ atunci ne intereseaza prefixul maxim al subsecventei $S[i+1..n]$ care se potriveste cu prefixul subsecventei $S[1..i]$ reflectate. Pentru a rezolva cu usurinta aceasta problema sortam impreuna si sufixele sirului cu prefixele reflectate ale sirului (operatie care se realizeaza usor concatenand sirul $S§$ cu sirul $S$ oglindit, $S^'^$) si vom efectua interogari pentru cel mai lung prefix comun pentru $S[i+1]$ si $S^'^[n-i+1]$ $(S^'^[n-i+1] = S[1..i])$, la care putem raspunde folosind siruri de sufixe in timp $O(1)$. Astfel, putem rezolva problema in timp $O(N log N)$. Sa observam ca am tratat aici doar cazul in care palindromul este de lungime para, dar cazul in care palindromul are lungime impara se trateaza analog.

h3. *Problema 8*: _Template_ (Olimpiada poloneza 2004, enunt modificat)

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:

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 = babaabaabaabaaab$, $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$

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

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