Cod sursa(job #638595)

Utilizator lily3Moldovan Liliana lily3 Data 21 noiembrie 2011 00:00:31
Problema PalM Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<fstream>
#include<cstring>
using namespace std;

int i,j,n,d[501][501],m,l[501],n2,rez,max1=0,ok1,max2;
char a[501],b[501],c,p[501];
int verif(int x,int rez)
{
	int i,y,ok=1,j;
	y=x+rez;
	max2=rez*2;
	for(i=y,j=y-1;i<=y+rez-1&&ok;++i,--j)
		if(p[j]!=p[i])
			ok=0;
		if(ok)
		return 1;
		ok=1;
		ok1=1;
	y=x+rez-1;
	max2=rez*2-1;
	for(i=y,j=y;i<=y+rez-1;++i,--j)
		if(p[j]!=p[i])
		    return 0;
			return 1;
}
int main()
{
	FILE *f=fopen("palm.in","r");
	FILE *g=fopen("palm.out","w");
	i=1;
	while(!feof(f)&&c!='\n')
	{
		fscanf(f,"%c",&c);
		a[i++]=c;
	}
	n=i-1;
	for(i=1;i<=n;i++)
		b[n-i]=a[i];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(a[i]==b[j])
				d[i][j]=d[i-1][j-1]+1;
			else
				d[i][j]=max(d[i-1][j],d[i][j-1]);
			i=j=n;
			while(i>=1)
				if(a[i]==b[j])
					p[++m]=a[i],l[m]=(int)p[m-1]-(int)p[m],j--,i--;
				else
					if(d[i-1][j]>d[i][j-1])
						i--;
					else
						j--;
					if(m%2)
						n2=m/2+1;
					else
						n2=m/2;
					i=1;
					rez=max1=1;
					while(i<n2)
					{
						if(int(p[i])<=int(p[i+1]))
							++i,++rez;
						else
							++i,rez=1;
						if(max1<rez&&verif(i-rez+1,rez))
							max1=rez;
						}
							fprintf(g,"%d",max2);
			return 0;
}