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