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.
 
h3. *Problema 8*: _Template_ (Olimpiada poloneza 2004, enunt modificat)
 
Pentru un string $A$, sa se determine lungimea minima a unui substring $B$ cu proprietatea ca $A$ poate fi obtinut prin lipirea intre ele a mai multor stringuri $B$ (la lipire doua stringuri se pot suprapune, dar in locurile in care se suprapun caracterele celor doua stringuri trebuie sa coincida).
 
h4. Exemplu
 
Pentru string-ul $ababbababbabababbabababbababbaba$ rezultatul este $8$. String-ul $B$ de lungime minima este $ababbaba$. $A$ poate fi obtinut din $B$ astfel:
 
$*ababbababbabababbabababbababbaba*$
$ababbaba$
$.....ababbaba$
$............ababbaba$
$...................ababbaba$
$........................ababbaba$
 
h3. Solutia 1:
 
O solutie simpla foloseste siruri de sufixe, un arbore echilibrat si un $max-heap$ (se pot folosi structurile $set$ si $priority_queue$ din $STL$). Este evident ca sablonul cautat este un prefix al lui $A$. Asadar, pentru fiecare prefix $B$ al lui $A$ vom verifica daca prin lipirea tuturor aparitiilor lui $B$ in $A$ se obtine chiar cuvantul initial $A$. Pentru a face aceasta verificare este suficient calculul distantei dintre perechile de potriviri consecutive ale lui $B$. Trebuie sa avem grija ca prefixele sa acopere si sfarsitul sirului. Pentru aceasta, cel mai comod este sa mai consideram o aparitie a lui $B$ pe pozitia $n+1$. Daca distanta maxima gasita este mai mare decat lungimea lui $B$, acel prefix nu reprezinta o solutie. Pentru o rezolvare eficienta, vom considera initial $B$ ca fiind prefixul de lungime $1$, urmand sa introducem la sfarsitul sau, caracter cu caracter, restul caracterelor string-ului $A$. Daca la fiecare pas mentinem multimea $S$ a pozitiilor de inceput ale potrivirilor lui $B$ in $A$, dupa introducerea unui nou caracter in $B$, multimea $S$ va "pierde" anumite elemente (posibil niciunul). Pentru administrare eficienta, vom considera sirul sortat de sufixe ale lui $A$ si doi pointeri, $L$ si $R$, reprezentand primul, respectiv ultimul sufix din sir care il au ca prefix pe $B$. La adaugarea unui nou caracter in $B$, se incrementeaza, respectiv decrementeaza $L$ si $R$ cat timp acestea nu indica sufixe care il au ca prefix pe noul $B$. Arborele echilibrat va contine tot timpul pozitiile de inceput ale sufixelor continute intre $L$ si $R$, iar $heap-ul$ va contine distantele intre elemente consecutive ale arborelui. La inserarea unui nou caracter in $B$, trebuie sa avem grija de intretinerea acestor structuri. Algoritmul se incheie atunci cand cel mai mare (primul) element din $heap$ este mai mic sau egal cu lungimea lui $B$. Lungimea finala a lui $B$ ne ofera rezultatul cautat. Ordinul de complexitate este $O(N lg N)$, unde $N$ este lungimea lui $A$. Sa consideram un exemplu. $S$ este marcat cu $1$ in pozitiile in care s-a gasit o potrivire a lui $B$ in $A$:
 
$1: aab$
$2: aabaab$
$3: ab$
$4: abaab$
$5: abaabaab$
$6: b$
$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;$
 

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.