$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)
 
Se considera un sir de caractere $S$ de lungime $n$ $(1 ≤ n ≤ 20000)$. Determinati subsecventa de lungime maxima care este si palindrom (un sir de caractere este palindrom daca este identic cu sirul obtinut prin oglindirea sa).
 
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.