Pagini recente » Cod sursa (job #1821950) | Cod sursa (job #2206294) | Cod sursa (job #2268772) | Cod sursa (job #280545) | Cod sursa (job #2189490)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char sir1[1000010],sir[2000010];
int d[2000010];
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
gets(sir1+1);
int n=0,l=strlen(sir1+1);
for(int i=1;i<=l;i++)
{
sir[++n]=sir1[i];
sir[++n]='*';
}
n--;
int lmax=0,poz=0;
for(int i=1;i<=n;i++)
{
if(i+d[i]<poz+lmax) d[i]=min(poz+lmax-i,d[2*poz-i]);
if(i+d[i]>=poz+lmax) while(i+d[i]<n && i-d[i]>1 && sir[i+d[i]+1]==sir[i-d[i]-1]) d[i]++;
if(i+d[i]>poz+lmax) {poz=i;lmax=d[i];}
}
long long sol=0;
for(int i=1;i<=n;i++)
if(sir[i]!='*') sol+=d[i]/2+1;
else
{
if(d[i]%2==0) sol+=d[i]/2;
else sol+=d[i]/2+1;
}
printf("%lld",sol);
return 0;
}