Cod sursa(job #644979)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 7 decembrie 2011 22:02:12
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Nmax 1000002

using namespace std;


char v[Nmax];

int l[2*Nmax];

long long sol;

int main(){
	
	freopen("pscpld.in","r",stdin);
	freopen("pscpld.out","w",stdout);
	
	fgets(v,Nmax,stdin);
	
	int N=strlen(v)-1;
	
	for(int i=0;i<=2*N;++i){
		
		int d=(l[i]/2);
		bool ok=0;
		
		while( i+d+1<2*(N+1) && d < i-l[i] && i/2+d+1<=N && i/2-d-1 + i%2>=0 && v[i/2+d+1]==v[i/2-d-1 + i%2] ){
			++d;
			ok=1;
		}
		
		for(int j=d;j>l[i]/2;--j){
			l[i+2*j]=min(l[i-2*j],2*(d-j)+1);
			l[i+2*j-1]=min(l[i-2*j+1],2*(d-j+1));
		}
        
		if(ok || l[i]==0)
			l[i]=2*d+(1-i%2);
	
		sol+=l[i]/2+1-i%2;

}
	printf("%lld",sol);
	
return 0;
}