Pagini recente » Cod sursa (job #2990722) | Cod sursa (job #208700) | Cod sursa (job #1249638) | Cod sursa (job #1655813) | Cod sursa (job #928617)
Cod sursa(job #928617)
#include<fstream>
#include<algorithm>
#include<string>
using namespace std;
const int NM=2000005;
string q,s;
int d[NM],p[NM];
int main(){
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int l,i,i1,j1,len; long long sol=0LL;
getline(cin,q); l=q.length(); s=" ";
for(i=0;i<l-1;++i){ s+=q[i]; s+=" "; }
s+=q[l-1];
l=2*l-1;
//cout<<s<<'\n';
for(i=1;i<=l;++i){
if(p[i])len=d[2*p[i]-i];
else len=0;
i1=j1=i;
while(i1-len>1 && j1+len<l && s[i1-len-1]==s[j1+len+1]){ ++len; if(!p[j1+len])p[j1+len]=i; }
if(s[i]==' '){ d[i]=((len+1)/2)*2; sol+=(d[i]/2); }
else { d[i]=(len/2)*2 +1; sol+=(d[i]/2)+1; }
}
//for(i=1;i<=l;++i)cout<<d[i]<<' ';
cout<<sol;
return 0;
}