Cod sursa(job #2387534)

Utilizator shantih1Alex S Hill shantih1 Data 24 martie 2019 20:19:59
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=1000*1000+5;
int p[2*nmax];
char s[2*nmax];
long long ans;
string ini;
int n,i,j,nr,r,c;
int main()
{
	ifstream f("pscpld.in");
	ofstream g("pscpld.out");
	f>>ini;ans=ini.size();
	s[nr++]='#';
	for(i=0;i<ini.size();i++)
	{
		s[nr++]=ini[i];
		s[nr++]='#';
	}
	r=c=-1;
	for(i=0;i<nr;i++)
	{
		if(i<=r) p[i]=min(p[2*c-i],r-i);
		while(i-p[i]>=0&&i+p[i]<nr&&s[i-p[i]]==s[i+p[i]])
			p[i]++;
		p[i]--;
		if(i+p[i]>r) r=i+p[i],c=i;
		ans+=1LL*p[i]/2;
	}
	g<<ans;
	
	/*ifstream f("pscpld.in");
	 ofstream g("pscpld.out");
	 f>>ini;ans=ini.size();
	 s[nr++]='#';
	 for(i=0;i<ini.size();i++)
	 {
		s[nr++]=ini[i];
		s[nr++]='#';
	 }
	 r=c=-1;
	 for(i=0;i<nr;i++)
	 {
		if(i<=r) p[i]=min(p[2*c-i],r-i);
		while(i-p[i]>=0&&i+p[i]<nr&&s[i-p[i]]==s[i+p[i]])
	 p[i]++;
		p[i]--;
		if(i+p[i]>r) r=i+p[i],c=i;
		ans+=1LL*p[i]/2;
	 }
	 g<<ans;*/
	
	return 0;
}