Cod sursa(job #910873)

Utilizator crushackPopescu Silviu crushack Data 11 martie 2013 09:59:55
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMax 1000010
using namespace std;

const char IN[]="pscpld.in",OUT[]="pscpld.out";

int N,Rez;
int T[2*NMax];
char s[2*NMax];

int main()
{
	int l,i,j,p;
	freopen(IN,"r",stdin);
	scanf("%s",s+1);
	fclose(stdin);

	N=strlen(s+1);

	for (i=N;i>0;--i)
		s[2*i-1]=s[i],s[2*i-2]='#';

	p=0,l=0;T[0]=1;
	for (i=1,l=0;i<=2*N;++i){

		T[i]=1;

		if (i<=l){
			T[i]=min(l-i+1,T[2*p-i]);
		}

		for (j=i+T[i];2*i-j>=0 && j<=N && s[j]==s[2*i-j];)
			++j;
		--j;
		T[i]=j-i+1;
		if (i+T[i]-1>l)
			p=i,
			l=i+T[i]-1;

		if (i%2) Rez+=T[i]/2;
		else Rez+=(T[i]+1)/2;
	}

	freopen(OUT,"w",stdout);
	printf("%d\n",Rez);
	fclose(stdout);

	return 0;
}