h3. Solutia 2

Vom incerca sa calculam valorile $pmin[i]$ treptat. Vom parcurge pozitiile de la $1$ la $N$ si vom incerca sa incepem un palindrom avand centrul in pozitia $i$ (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile $i$ si $i+1$ (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia $i$, toate valorile $pmin[j]$, cu $j < i$ au fost calculate, iar valorile $pmin[k]$, $k > i$, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei $i$ (respectiv pozitiilor $i$ si {$i+1$}); la fiecare pas de extindere, vom incerca sa incrementam palindromul de la lungimea curenta $L$, la lungimea $L+2$ (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea $pmin[i-(L+1)/2]+1$ sa fie folosita pentru a micsora valoarea lui $pmin[i+(L+1)/2-1]$ (pentru cazul lungimii impare), respectiv valoarea $pmin[i-L/2]+1$ poate fi folosita pentru a micsora valoarea lui $pmin[i+L/2]$ (pentru cazul lungimii pare).

Vom incerca sa calculam valorile $pmin[i]$ treptat. Vom parcurge pozitiile de la $1$ la $N$ si vom incerca sa incepem un palindrom avand centrul in pozitia $i$ (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile $i$ si $i+1$ (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia $i$, toate valorile $pmin[j]$, cu $j < i$ au fost calculate, iar valorile $pmin[k]$, $k > i$, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei $i$ (respectiv pozitiilor $i$ si {$i+1$}); la fiecare pas de extindere, vom incrementa palindromul de la lungimea curenta $L$, la lungimea $L+2$ (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea $pmin[i-(L+1)/2]+1$ sa fie folosita pentru a micsora valoarea lui $pmin[i+(L+1)/2-1]$ (pentru cazul lungimii impare), respectiv valoarea $pmin[i-L/2]+1$ poate fi folosita pentru a micsora valoarea lui $pmin[i+L/2]$ (pentru cazul lungimii pare).

Complexitatea ambelor solutii este $O(N^2^)$, insa a doua solutie merge mai repede, in practica, deoarece ia in considerare numai palindroamele valide (care pot fi cel mult {$O(N^2^)$}).