Cod sursa(job #919029)

Utilizator raulstoinStoin Raul raulstoin Data 19 martie 2013 12:29:15
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<fstream>
#include<cstring>
#define NMAX 1000005
#define min(a,b) a<b?a:b
using namespace std;
char x[NMAX];
int n,m,DP[NMAX];
long long sol;
void read()
{
	ifstream fin("pscpld.in");
	fin>>x+1;
	x[0]=' ';
	n=strlen(x)-1;
	fin.close();
}
int expand(int left,int right)
{
	int L=0;
	for(;left && right<=n & x[left]==x[right];left--,right++)
		L++;
	return L;
}
void manacher(int par)
{
	int p=0,r=0,left,right;
	memset(DP,0,4*(n+2));
	for(int i=1;i<=n;i++)
	{
		if(par && x[i]!=x[i+1])
			continue;
		if(r>=i+par)
			DP[i]=min(DP[p-(i-p)],r-i-par);
		left=i-DP[i];
		right=i+DP[i]+par;
		DP[i]+=expand(left,right);
		if(i+DP[i]+par>r)
		{
			r=i+DP[i]+par;
			p=i;
		}
		sol+=DP[i];
	}
}
void print()
{
	ofstream fout("pscpld.out");
	fout<<sol<<'\n';
	fout.close();
}
int main()
{
	read();
	manacher(0);
	manacher(1);
	print();
	return 0;
}