Cod sursa(job #639193)

Utilizator ChallengeMurtaza Alexandru Challenge Data 22 noiembrie 2011 18:36:20
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <cstring>

using namespace std;

const char InFile[]="pscpld.in";
const char OutFile[]="pscpld.out";
const int MaxN=1000111;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,st,dr,A[MaxN];
long long sol;
char S[MaxN];

int main()
{
	fin>>(S+1);
	fin.close();
	
	N=strlen((S+1));
	
	st=dr=1;
	for(register int i=1;i<=N;++i)
	{
		if(i<=dr)
		{
			A[i]=min(A[st+dr-i],dr-i);
			for(st=i-A[i],dr=i+A[i];st>1 && dr<N && S[st-1]==S[dr+1];--st,++dr,++A[i]);
		}
		else
		{
			for(st=dr=i;st>1 && dr<N && S[st-1]==S[dr+1];--st,++dr,++A[i]);
		}
		sol+=A[i]+1;
	}
	
	st=1;dr=2;
	for(register int i=1;i<N;++i)
	{
		if(S[i]==S[i+1])
		{
			if(i<=dr)
			{
				A[i]=min(A[st+dr-i-1],dr-i-1);
				for(st=i-A[i],dr=i+1+A[i];st>1 && dr<N && S[st-1]==S[dr+1];--st,++dr,++A[i]);
			}
			else
			{
				for(st=i,dr=i+1;st>1 && dr<N && S[st-1]==S[dr+1];--st,++dr,++A[i]);
			}
			sol+=A[i]+1;
		}
		else
		{
			A[i]=0;
		}
	}
	
	fout<<sol;
	fout.close();
	return 0;
}