Pagini recente » Monitorul de evaluare | Cod sursa (job #1001346) | Monitorul de evaluare | Cod sursa (job #385963) | Cod sursa (job #1650656)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int d[2000010];
char sir[2000010];
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
scanf("%s",sir+1);
int n=strlen(sir+1),nr=2*n,mid=0,lim=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<=lim) d[i]=min(lim-i,d[2*mid-i]);
while(1<=i-d[i]-1 && i+d[i]+1<=n && sir[i-d[i]-1]==sir[i+d[i]+1]) d[i]++;
if(i+d[i]>lim) {mid=i;lim=i+d[i];}
}
for(int i=1;i<=n;i++) sol+=(d[i]+1)/2;
printf("%lld",sol);
return 0;
}