Pagini recente » Cod sursa (job #1102651) | Cod sursa (job #2047706) | Cod sursa (job #331286) | Cod sursa (job #1560298) | Cod sursa (job #2047001)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lim 2000010
int d[lim],n,nr,mid,maxm;
char sir[lim];
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
scanf("%s",sir+1);
n=strlen(sir+1);
nr=2*n;
mid=0;
maxm=0;
long long sol=0;
for (int i=n; i; i--)
{
sir[nr--]=sir[i];
sir[nr--]='*';
}
n=2*n+1;
sir[n]='*';
for (int i=1; i<=n; i++)
{
if (i<=maxm) d[i] = min (maxm-i, d[2*mid-i]);
while (i-d[i]>=2 && i+d[i]<=n-1 && sir[i-d[i]-1]==sir[i+d[i]+1]) d[i]++;
if (i+d[i]>maxm)
{
mid=i;
maxm=i+d[i];
}
}
for (int i=1; i<=n; i++) sol += (d[i]+1)/2;
printf("%lld",sol);
return 0;
}