Pagini recente » Cod sursa (job #1650669) | Cod sursa (job #2782041) | Cod sursa (job #2054096) | Cod sursa (job #1999122) | Cod sursa (job #1787771)
#include <cstdio>
#include <cstring>
#define NMax 2000005
#define MIN(a,b)((a)<(b)?(a):(b))
char s[NMax+1];
char v[NMax+1];
int best[NMax+1];
int N,t;
void Update()
{
int i,t;
for(t = 1, i = 0; i < N; ++i)
{
v[t++] = s[i];
v[t++] = '#';
}
v[0] = '#';
v[--t] = '#';
N = --t;
}
int main(){
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
int R,C,i,ii,j;
long long ans = 0;
fgets(s, NMax-1, stdin);
N = strlen(s);
if(s[N-1]=='\n') --N;
Update();
R = C = 0;
for(i = 1; i <= N; ++i)
{
ii = 2*C-i;
best[i] = ( R>i? MIN( best[ii], R-i ) : 0 );
j = best[i];
while( v[i+j] == v[i-j] && (i+j<=N+1) && (i>=j) ) ++j;
--j;
best[i] = j;
if( i + j > C + R )
{
R = j;
C = i;
}
}
for(i = 1; i <= N; ++i)
if( v[i] == '#' ) ans = ans + best[i]/2;
else ans = ans + best[i]/2 + 1;
printf("%lld\n",ans);
return 0;
}