Cod sursa(job #1065346)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 23 decembrie 2013 11:20:36
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
char A[1000001];
char X[2000005];
int n,i;
int P[2000005];
int id,mx;
long long rez;
int main()
{
	fi>>A;
	X[0]='$';
	X[1]='#';
	n=2;
	for (i=0;A[i]!='\0';i++)
	{
		X[n++]=A[i];
		X[n++]='#';
	}
	X[n]='\0';
	P[0]=1;
	P[1]=1;
	id=1;
	mx=1;
	for (i=2;i<n;i++)
	{
		P[i]= mx > i ? min(P[2*id-i], mx-i) : 1;
		while (X[i + P[i]] == X[i - P[i]])
			P[i]++;
		if (i + P[i] > mx)
		{
			mx = i + P[i];
			id = i;
		}
	}
	rez=0;
	for(i=1;i<n;i++)
		rez+=(P[i]/2);
	fo<<rez<<'\n';
	fi.close();
	fo.close();
	return 0;
}