Cod sursa(job #960286)

Utilizator predatorGigi Valoare predator Data 10 iunie 2013 09:20:18
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<fstream>
#include<cstring>
#define NM 1000100
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int D[NM],i,dr,rig,lef,n,p,ii,S;
char s[NM];
int main ()
{
	f>>(s+1);
	n=strlen(s+1);
	for(i=1;i<=n;++i)
	{
		if(dr>i)
		{
			ii=p-(i-p);
			if(D[ii]/2+i<dr)
				D[i]=D[ii];
			else
			{
				lef=i-D[ii]/2;
				rig=i+D[ii]/2;
				if(rig>n)
					rig--,lef++;
				while(s[lef]==s[rig]&&lef)
				{
					lef--;
					rig++;
				}
				lef++;
				rig--;
				D[i]=rig-lef+1;
				p=i;
				dr=rig;
			}
		}
		else
		{
			lef=rig=i;
			while(s[lef]==s[rig]&&lef)
			{
				lef--;
				rig++;
			}
			lef++;
			rig--;
			D[i]=rig-lef+1;
			p=i;
			dr=rig;
		}
	}
	for(i=1;i<=n;++i)
	{
		S+=(D[i]+1)/2;
		D[i]=0;
	}
	dr=p=0;
	for(i=1;i<n;++i)
	{
		if(dr>i)
		{
			ii=p-(i-p);
			if(D[ii]/2+i<dr)
				D[i]=D[ii];
			else
			{
				lef=i-(D[ii]-1)/2;
				rig=i+D[ii]/2;
				if(rig>n)
					rig--,lef++;
				while(s[lef]==s[rig]&&lef)
				{
					lef--;
					rig++;
				}
				lef++;
				rig--;
				D[i]=rig-lef+1;
				p=i;
				dr=rig;
			}
		}
		else
		{
			lef=i;
			rig=i+1;
			if(s[lef]!=s[rig])
				continue;
			else
			{
				while(s[lef]==s[rig])
				{
					lef--;
					rig++;
				}
				lef++;
				rig--;
			}
			D[i]=rig-lef+1;
			p=i;
			dr=rig;
		}
	}
	for(i=1;i<=n;++i)
		S+=D[i]/2;
	g<<S;
	return 0;
}