Pagini recente » Cod sursa (job #1978178) | Cod sursa (job #1310746) | Cod sursa (job #1502240) | Cod sursa (job #523114) | Cod sursa (job #637286)
Cod sursa(job #637286)
#include <fstream>
using namespace std;
const int N=501,C=26;
short int v[N][N][C],n;
char a[N],b[N];
ifstream in("palm.in");
ofstream out("palm.out");
void inv(char b[],char a[])
{
for (int j=n,i=1;i<=n;i++,j--)
b[j]=a[i];
}
void copy(short int v[],short int a[],short int b[])
{
for (int i=0;i<C;i++)
v[i]=a[i]>b[i] ? a[i] : b[i];
}
void copy(short int v[],short int a[],short int b[],short int g[],int p)
{
for (int i=0;i<C;i++)
v[i]=a[i]>b[i] ? a[i] : b[i];
for (int i=p;i<C;i++)
v[i]=g[p]+1>v[i] ? g[p]+1 : v[i];
}
int cmlscc()
{
int rez=0,i,j;
for (i=1;i<=n;i++)
{
for (j=1;j<=n-i+1;j++)
if (a[i]!=b[j])
copy(v[i][j],v[i-1][j],v[i][j-1]);
else
copy(v[i][j],v[i-1][j],v[i][j-1],v[i-1][j-1],a[i]-'a');
if (2*v[i][n-i][C-1]>rez)
rez=2*v[i][n-i][C-1];
if (2*v[i][n-i+1][C-1]>rez)
rez=2*v[i][n-i+1][C-1]-1;
}
return rez;
}
int main()
{
in>>(a+1);
for (n=1;a[n];n++);
n--;
inv(b,a);
out<<cmlscc()<<"\n";
return 0;
}