Pagini recente » Istoria paginii runda/pa-test1-2019-22/clasament | Cod sursa (job #594566) | Cod sursa (job #1715025) | Cod sursa (job #1721880) | Cod sursa (job #1786540)
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
char s[1000010],sir[2000010];
int d[2000010];
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;
}