Cod sursa(job #485468)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 18 septembrie 2010 14:36:09
Problema PScPld Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <cstring>
#define MAXLIM 1000020
using namespace std;
int N;
char S[MAXLIM*2];
char S2[MAXLIM];
int ext[MAXLIM];


int main(){

	freopen("pscpld.in","r",stdin);
	freopen("pscpld.out","w",stdout);

	fgets(S2+1,MAXLIM,stdin);

	N=strlen(S2+1);

	while (S2[N]<'a' || S2[N]>'z') --N;

	fclose(stdin);

	int N2=0;

	for (int i=1;i<N;++i){
		++N2;
		S[N2]=S2[i];
		++N2;
		S[N2]='*';
	}

	++N2;
	S[N2]=S2[N];

	N=N2;


	long long csum=1;
	int lowint=1;
	int highint=1;
	ext[1]=1;

	for (int i=2;i<=N;++i)
		if (i>highint){
			int cst=i-1;
			int cdr=i+1;

			while (cdr<=N && cst>=1 && S[cst]==S[cdr]){
				--cst;
				++cdr;
			}

			++cst;
			--cdr;

			ext[i]=i-cst+1;
			if (S[i]=='*') csum+=ext[i]/2; else csum+=ext[i]/2+ext[i]%2;

			if (cdr>highint){
				lowint=cst;
				highint=cdr;
			}
		} else {
			
			int j=lowint+highint-i;

			ext[i]=ext[j];

			if ((highint-i+1)<ext[i]) ext[i]=highint-i+1;

			int cst=i-ext[i];
			int cdr=i+ext[i];

			while (cdr<=N && cst>=1 && S[cst]==S[cdr]){
				--cst;
				++cdr;
			}

			++cst;
			--cdr;

			ext[i]=i-cst+1;
			if (S[i]=='*') csum+=ext[i]/2; else csum+=ext[i]/2+ext[i]%2;

			if (cdr>highint){
				lowint=cst;
				highint=cdr;
			}
		}
	
	printf("%lld\n",csum);


	fclose(stdout);

	return 0;
}