Pagini recente » Cod sursa (job #2619735) | Cod sursa (job #1234297)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int sol[2000010],n,i,mid,lim;
char v[2000010];
long long rez;
int main()
{
freopen("pscld.in", "r", stdin);
freopen("pscld.out", "w", stdout);
scanf("%s",v+1);
n=strlen(v+1);
for(i=n;i;i--)
{
v[2*i]=v[i];
v[2*i-1]='#';
}
n=2*n+1;
v[n]='#';
mid=lim=1;
for(i=2;i<=n;i++)
{
if(i<=lim) sol[i]=min(sol[mid-(i-mid)],lim-i);
while(1<=i-sol[i]-1 && i+sol[i]+1<=n && v[i-sol[i]-1]==v[i+sol[i]+1]) sol[i]++;
if(i+sol[i]>lim)
{
lim=i+sol[i];
mid=i;
}
}
for(i=1;i<=n;i++)
if(i%2) rez+=(sol[i]+1)/2;
else rez+=(sol[i]+2)/2;
printf("%lld",rez);
return 0;
}