Pagini recente » Cod sursa (job #540422) | Cod sursa (job #914506) | Cod sursa (job #469607) | Cod sursa (job #2946294) | Cod sursa (job #928782)
Cod sursa(job #928782)
#include<fstream>
#include<algorithm>
#include<string>
using namespace std;
const int NM=2000005;
string s;
int d[NM],p[NM];
int main(){
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int l,i,j,len,ll,p; long long sol=0LL;
getline(cin,s); l=s.length(); s=" "+s;
s.resize(2*l+1);
for(i=l;i>0;--i){ s[i*2]=' '; s[i*2-1]=s[i]; }
l=2*l-1; ll=0; p=0; d[0]=1;
//cout<<s<<'\n';
for(i=1;i<=l;++i){
d[i]=1;
if(i<=ll)
d[i]=min(d[2*p-i],ll-i+1);
j=i+d[i];
while(2*i-j>=0 && j<=l && s[2*i-j]==s[j])++j;
--j;
d[i]=j-i+1;
if(i+d[i]-1>ll){ ll=i+d[i]-1; p=i; }
if(i&1) sol+=(d[i]+1)/2;
else sol+=(d[i]/2);
}
//for(i=1;i<=l;++i)cout<<d[i]<<' ';
cout<<sol;
return 0;
}