Cod sursa(job #1003843)

Utilizator dariusdariusMarian Darius dariusdarius Data 1 octombrie 2013 18:26:45
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<fstream>
#include<string>
#include<algorithm>
using namespace std;
string in,s;
int p[2000005];
int main()
{
	ifstream cin("pscpld.in");
	ofstream cout("pscpld.out");
	cin>>in;
	s="+";
	for(int i=0;i<(int)in.size();i++)
	{
		s+='#';
		s+=in[i];
	}
	s+="#-";
	int c=0,r=0;
	for(int i=1;i<(int)s.size()-1;i++)
	{
		int j=2*c-i;
		if(i<r)
			p[i]=min(r-i,p[j]);
		else
			p[i]=0;
		while(i+p[i]+1<(int)s.size() && i-p[i]-1>=0 && s[i+p[i]+1]==s[i-p[i]-1])
			p[i]++;
		if(i+p[i]>r)
		{
			c=i;
			r=i+p[i];
		}
	}
	long long ans=0;
	for(int i=1;i<(int)s.size()-1;i++)
		ans+=(p[i]+1)/2;
	cout<<ans<<endl;
	return 0;
}