Cod sursa(job #2041086)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 16 octombrie 2017 20:41:30
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
char T[1000002],S[2000005];
int P[2000005];
int n,m,id,mx;
long long rez;
int main()
{
	fi>>T+1;
	n=strlen(T+1);
	/// se formeaza S
	for (int i=1;i<=n;i++)
		S[2*i]=T[i];
	for (int i=1;i<=2*n+1;i=i+2)
		S[i]='*';
	S[0]='+';
	S[2*n+2]='-';
	S[2*n+3]='\0';
	m=2*n+1;
	P[1]=1;
	id=1;
	mx=1;
	for (int i=2;i<=m;i++)
	{
		if (i<=mx)
			P[i]=min(P[2*id-i],mx-i+1);
		else
			P[i]=1;
		while (S[i+P[i]]==S[i-P[i]])
			P[i]++;
		if (i+P[i]-1>mx)
		{
			id=i;
			mx=i+P[i]-1;
		}
	}
	/*
	for (int i=1;i<=m;i++)
		fo<<S[i];
	fo<<"\n";
	for (int i=1;i<=m;i++)
		fo<<P[i];
	*/
	rez=0LL;
	for (int i=1;i<=m;i++)
		if (i%2==1)
			rez=rez+(P[i]-1)/2;
		else
			rez=rez+P[i]/2;
	fo<<rez;
	fi.close();
	fo.close();
	return 0;
}