Pagini recente » Cod sursa (job #1433073) | Cod sursa (job #3274720) | Cod sursa (job #1874627) | Cod sursa (job #910753) | Cod sursa (job #1786539)
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
char s[1000010],sir[1000010];
int d[1000010];
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
int n,l,lmax,a,b,r,mid=0;
long long sol=0;
scanf("%s",s+1);
n=strlen(s+1);
l=0;
for(int i=1;i<n;i++)
{
l++;
sir[l]=s[i];
l++;
sir[l]='*';
}
l++;sir[l]=s[n];
lmax=0;
for(int i=1;i<=l;i++)
{
if(i<=lmax) d[i]=min(d[mid-(i-mid)],lmax-i);
a=i-d[i]-1;
b=i+d[i]+1;
r=0;
while(a>=1 && b<=l && sir[a]==sir[b]) {r++;a--;b++;}
d[i]+=r;
if(i+d[i]>lmax) {lmax=i+d[i];mid=i;}
}
for(int i=1;i<=l;i++)
if(sir[i]!='*') sol=sol+d[i]/2+1;
else
{
if(d[i]%2==1) sol=sol+d[i]/2+1;
else sol=sol+d[i]/2;
}
printf("%lld",sol);
return 0;
}