Cod sursa(job #784366)

Utilizator misinozzz zzz misino Data 5 septembrie 2012 16:23:24
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include<fstream>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int l,poz,i,n,p[2000001];
char s[1000001],a[2000001];
long long nr=1;
int main()
{f>>s;
n=strlen(s);
for(i=0;i!=n;++i)
{a[2*i]=' ';
a[2*i+1]=s[i];
}
n=2*n-1;
poz=1;
l=1;
p[0]=p[1]=1;

for(i=2;i<=n;++i)
{p[i]=1;
if(poz+l-1>i)
	p[i]=min(p[2*poz-i],l+poz-i);
while(i>p[i]&&a[i-p[i]]==a[i+p[i]])
	++p[i];
if(i&1)
	nr+=(p[i]+1)/2;
else
	nr+=p[i]/2;
if(p[i]+i>l+poz)
{poz=i;
l=p[i];
}
}
g<<nr<<'\n';
return 0;
}