Cod sursa(job #636019)

Utilizator cosminx2003Cosmin Clapon cosminx2003 Data 19 noiembrie 2011 16:20:41
Problema PalM Scor 30
Compilator cpp Status done
Runda .com 2011 Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <string.h>
#define N 500
#define min(a,b) ((a>b)?b:a)
using namespace std;
ifstream f("palm.in");
ofstream g("palm.out");

inline int palindrom(char sir[N],int a,int b);

int main() {
	char s[N];
	int o[N]={0},r[N]={0},n,i,temp,max=0,tmp;
	
	f>>s;
	
	n=strlen(s)-1;
	o[0]=1,r[n]=1;
	for(i=1;i<=n;i++) {
		temp=s[i]-s[i-1];
		if(temp >= 0) {
			o[i]+=o[i-1]+1;
		} else {
			o[i]=1;
		}
		temp=s[n-i]-s[n-i+1];
		if(temp >= 0) {
			r[n-i]+=r[n-i+1]+1;
		}  else {
			r[n-i]=1;
		}
	}

	for(i=1;i<=n;i++) {
		if(o[i-1] < o[i] && r[i+1] < r[i]) {
			tmp=palindrom(s,i-o[i-1],i+r[i+1]);
			if(tmp>max) {
				max=tmp;
			}
		}
	}

	g<<max;
	
	f.close();
	g.close();
	return 0;
}

inline int palindrom(char sir[N],int a,int b) {
	int seqLen,i,max=0,s,lLen,e,k=0;
	char seq[N];
	for(i=a;i<=b;i++) {
		seq[k++]=sir[i];
	}
	seq[k]='\0';
	
	seqLen=strlen(seq);
	lLen=2*seqLen+1;
	for(i=0;i<lLen;i++) {
		s=i/2;
		e=s+i%2;
		while(s>0 && e<seqLen && seq[s-1]==seq[e]) {
			s-=1;
			e+=1;
		}
		if(e-s > max) {
			max=e-s;
		}
	}
	return max;
}