Pagini recente » Cod sursa (job #273661) | Cod sursa (job #480262) | Cod sursa (job #2133188) | Cod sursa (job #1578785) | Cod sursa (job #477476)
Cod sursa(job #477476)
#include <cstdio>
#include <cstring>
#define nmax 1000010
char s[nmax];
int lg[nmax], n;
long long sol;
int min(int a, int b)
{
if (a>b) a=b;
return a;
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
fgets(s,nmax,stdin);
n=strlen(s)-1;
int i, st, dr;
for (i=n; i>0; i--) s[i]=s[i-1];
for (i=1; i<=n; i++) lg[i]=1;
st=dr=0;
for (i=1; i<=n; i++)
{
if (dr>i)
lg[i]=min(lg[st+dr-i], dr-i+1);
if (i+lg[i]-1>=dr)
{
dr=i+lg[i]-1;
st=i-lg[i]+1;
while (s[st-1]==s[dr+1] && dr<n && st>1)
{
st--;
dr++;
lg[i]++;
}
}
sol+=lg[i];
}
st=dr=0;
for (i=1; i<=n; i++) lg[i]=0;
for (i=1; i<n; i++)
{
if (dr>i)
lg[i]=min(lg[st+dr-i-1], dr-i);
if (i+lg[i]>=dr)
{
dr=i+lg[i];
st=i-lg[i]+1;
while (s[st-1]==s[dr+1] && dr<n && st>1)
{
st--;
dr++;
lg[i]++;
}
}
sol+=lg[i];
}
printf("%lld\n",sol);
}