Pagini recente » Cod sursa (job #2942689) | Cod sursa (job #1858099) | Cod sursa (job #1833972) | Cod sursa (job #2671763) | Cod sursa (job #2293899)
#include <cstdio>
#include <algorithm>
using namespace std;
int pal[2000005];
char s[2000005];
int main()
{ freopen("pscpld.in", "r",stdin);
freopen("pscpld.out", "w",stdout);
int n,i,c,r,ii;
char ch;
long long sol=0;
ch=fgetc(stdin);
for(i=1; ch!='\n' && ch!=EOF; ch=fgetc(stdin),i+=2){
s[i-1]='*';
s[i]=ch;
}
n=i-2;
s[n+1]='*';
s[n+2]=0;
c,r=0;
for(i=2; i<=n; i++){
ii=2*c-1;
if(r>i)
pal[i]=min(r-i, pal[ii]);
else
pal[i]=0;
while(i-pal[i]-1>0 && i+pal[i]+1<=n && s[i-pal[i]-1]==s[i+pal[i]+1])
pal[i]++;
if(i+pal[i]>r){
r=i+pal[i];
c=i;
}
}
sol=0;
for(i=1; i<=n; i++){
sol+=pal[i]/2;
if(s[i]!='*')
sol++;
}
printf("%lld", sol);
return 0;
}