Pagini recente » Cod sursa (job #2880471) | Cod sursa (job #1405326) | Cod sursa (job #1335962) | Cod sursa (job #1566248) | Cod sursa (job #1322133)
#include<cstdio>
#include<cstring>
using namespace std;
const int NMAX=1000000;
char v[2*NMAX+10];
int p[2*NMAX+10];
int n;
void extend(int pos)
{
while(pos-p[pos]>0 && pos+p[pos]<=n && v[pos-p[pos]]==v[pos+p[pos]])
p[pos]++;
p[pos]--;
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",v+1);
n=strlen(v+1);
for(int i=n;i>=0;i--)
{
v[2*i+1]='#';
v[2*i]=v[i];
}
n=2*n+1;
int c=1;
for(int i=2;i<=n;i++)
{
int i2=2*c-i,st=c-p[c],dr=c+p[c];
if (i>dr)
{
extend(i);
c=i;
}
else
{
if (i2-p[i2]>st)
p[i]=p[i2];
else
{
p[i]=dr-i;
extend(i);
c=i;
}
}
}
long long ans=0;
for(int i=1;i<=n;i++)
ans+=(long long)p[i]/2;
printf("%lld\n",ans+n/2);
return 0;
}