Pagini recente » Cod sursa (job #1202946) | Cod sursa (job #219741) | Cod sursa (job #1524103) | Cod sursa (job #1292651) | Cod sursa (job #476561)
Cod sursa(job #476561)
#include <cstdio>
#include <cstring>
#define nmax 1000010
char s[nmax];
int v[2*nmax], n, t;
int min(int a, int b)
{
if (a>b) a=b;
return a;
}
int max(int a, int b)
{
if (a<b) a=b;
return a;
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",s);
n=strlen(s);
int i, k, j, c, x;
for (i=n; i>0; i--) s[i]=s[i-1];
for (i=1; i<=n; i++)
{
k=v[2*i-1];
for (j=k+1; j<=n-i+1 && j<=i; j++)
{
if (s[i+j-1]!=s[i-j+1]) break;
k=j;
}
v[2*i-1]=k;
for (j=1; j<k; j++)
{
x=i+j-1;
c=min(v[2*(i-j)],j);
c=min(c,k-j);
v[2*x]=max(v[2*x],c);
c=min(v[2*(i-j)-1], j+1);
c=min(c,k-j);
v[2*x+1]=max(v[2*x+1],c);
}
k=v[2*i];
for (j=k+1; j<=n-i && j<=i; j++)
{
if (s[i+j]!=s[i-j+1]) break;
k=j;
}
v[2*i]=k;
if (k)
{
c=min(v[2*i-1],1);
v[2*i+1]=max(v[2*i+1],c);
}
for (j=1; j<k; j++)
{
x=i+j;
c=min(v[2*(i-j)],j);
c=min(c,k-j);
v[2*x]=max(v[2*x], c);
c=min(v[2*(i-1)-1], j+1);
c=min(c, k-j);
v[2*x+1]=max(v[2*x+1], c);
}
}
for (i=1; i<=2*n; i++) t+=v[i];
printf("%d\n",t);
}