Pagini recente » Cod sursa (job #1513069) | Cod sursa (job #229931) | redsnow_2 | Cod sursa (job #2699080) | Cod sursa (job #84768)
Cod sursa(job #84768)
#include <stdio.h>
#include <string.h>
#define nmax 2111000
#define FOR(i,s,d) for(i=(s);i<(d);++i)
char s[nmax];
int n,poz,l,last,start,L[nmax];
long long sol;
inline int min(int a,int b) {return a<b?a:b;}
int main()
{
int i;
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",s);
n=strlen(s);
for(i=n;i>=0;--i)
s[2*i+1]=s[i],s[2*i]='#';
n=2*n+1;
poz=0, last=0, L[0]=0;
FOR(i,1,n)
{
if(last>=i)
L[i]=min(L[poz+poz-i],last-i);
else
L[i]=0;
for(;i+L[i]+1<n&&i-L[i]-1>=0&&s[i-L[i]-1]==s[i+L[i]+1];L[i]++);
if(i+L[i]>last)
last=i+L[i],poz=i;
sol+=(s[i]=='#'?(L[i]+1)/2:L[i]/2+1);
}
printf("%lld\n",sol);
return 0;
}