Pagini recente » Cod sursa (job #546572) | Cod sursa (job #2389399) | Cod sursa (job #2738387) | Cod sursa (job #2322874) | Cod sursa (job #887651)
Cod sursa(job #887651)
#include<cstdio>
#include<cstring>
#define min(a,b) ((a)<(b)?(a):(b))
char s[2000005];
int d[2000005];
int main (void)
{
freopen ("pscpld.in","r",stdin);
#ifdef INFOARENA
freopen ("pscpld.out","w",stdout);
#endif
gets (s);
int n=strlen (s);
for(int i=2*n;i>=0;i--)
s[i]=i%2?s[i/2]:'!';
n=n*2+1;
int mx=0;
for(int i=0;i<n;i++){
if(mx+d[mx]>=i)
d[i]=min (mx+d[mx]-i, d[2*mx-i]);
while(i-d[i]>=0&&i+d[i]<n&&s[i-d[i]]==s[i+d[i]])
d[i]++;
if(i+d[i]>=mx+d[mx])
mx=i;
}
long long ret=0;
for(int i=0;i<n;i++)
ret+=d[i]/2;
printf ("%lld",ret);
return 0;
}