Pagini recente » Rating nicolae dan (danik) | Cod sursa (job #710176) | Cod sursa (job #2250060) | Borderou de evaluare (job #148045) | Cod sursa (job #784366)
Cod sursa(job #784366)
#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;
}