Pagini recente » Cod sursa (job #395998) | Cod sursa (job #419970) | Cod sursa (job #328156) | Cod sursa (job #1135685) | Cod sursa (job #2537560)
#include <bits/stdc++.h>
#define DIM 510
using namespace std;
ifstream fin ("palm.in");
ofstream fout ("palm.out");
int dp[DIM][DIM],_next[DIM][30],_prv[DIM][30];
char v[DIM];
int n,i,j,lg,lit;
int main (){
fin>>v+1;
n = strlen (v+1);
/// dp[i][j] - cel mai lung palindrom dintre pozitiile i,j care are capetele fixate in i si j
for (i=1;i<=n;i++)
dp[i][i] = 1;
for (j=0;j<26;j++){
for (i=1;i<=n;i++){
if (v[i]-'a' == j)
_prv[i][j] = i;
else _prv[i][j] = _prv[i-1][j];
}
_next[n+1][j] = n+1;
for (i=n;i;i--){
if (v[i]-'a' == j)
_next[i][j] = i;
else _next[i][j] = _next[i+1][j];
}
}
int sol = 1;
for (lg=1;lg<=n;lg++){
for (i=1;i+lg<=n;i++){
j = i + lg;
if (v[i] != v[j])
dp[i][j] = 0;
dp[i][j] = 2;
for (lit=v[i]-'a';lit<26;lit++){
int poz1 = _next[i+1][lit];
int poz2 = _prv[j-1][lit];
if (poz1 <= poz2 && poz1 > i && poz2 < j)
dp[i][j] = max (dp[i][j],dp[poz1][poz2]+2);
}
sol = max (sol,dp[i][j]);
}}
fout<<sol;
return 0;
}