Cod sursa(job #477476)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 14 august 2010 23:05:04
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <cstring>
#define nmax 1000010

char s[nmax];
int lg[nmax], n;
long long sol;

int min(int a, int b)
{
	if (a>b) a=b;
	return a;
}

int main()
{
	freopen("pscpld.in","r",stdin);
	freopen("pscpld.out","w",stdout);
	fgets(s,nmax,stdin);
	n=strlen(s)-1;
	int i, st, dr;
	for (i=n; i>0; i--) s[i]=s[i-1];
	for (i=1; i<=n; i++) lg[i]=1;
	st=dr=0;
	for (i=1; i<=n; i++)
	{
		if (dr>i)
			lg[i]=min(lg[st+dr-i], dr-i+1);
		if (i+lg[i]-1>=dr)
		{
			dr=i+lg[i]-1;
			st=i-lg[i]+1;
			while (s[st-1]==s[dr+1] && dr<n && st>1) 
			{
				st--;
				dr++;
				lg[i]++;
			}
		}
		sol+=lg[i];
	}
	st=dr=0;
	for (i=1; i<=n; i++) lg[i]=0;
	for (i=1; i<n; i++)
	{
		if (dr>i)
			lg[i]=min(lg[st+dr-i-1], dr-i);
		if (i+lg[i]>=dr)
		{
			dr=i+lg[i];
			st=i-lg[i]+1;
			while (s[st-1]==s[dr+1] && dr<n && st>1) 
			{
				st--;
				dr++;
				lg[i]++;
			}
		}
		sol+=lg[i];
	}
	printf("%lld\n",sol);
}