Pagini recente » Cod sursa (job #994403) | Cod sursa (job #1026371) | Cod sursa (job #1910720) | Cod sursa (job #1850861) | Cod sursa (job #639688)
Cod sursa(job #639688)
#include<stdio.h>
#include<cstring>
#define maxn 1000005
FILE*f=fopen("pscpld.in","r");
FILE*g=fopen("pscpld.out","w");
int n,st,dr,i,j; long long nrpal;
int D[maxn<<1];
char sir[maxn];
inline int min ( int a , int b ){
return a <= b ? a : b;
}
int main () {
fscanf(f,"%s",sir+1);
n = strlen(sir+1);
st = 1; dr = 0;
for ( i = 1 ; i <= n + n ; ++i ){
j = (i+1)>>1;
if ( (!(i & 1)) && sir[j] != sir[j+1] ) continue ;
if ( j <= dr ){
if ( i & 1 )
D[i] = min(D[((st+dr-j)<<1)-1],dr-j);
else
D[i] = min(D[((st+dr-j)<<1)-2],dr-j);
if ( D[i] + j >= dr ){
if ( i & 1 ){
st = j - D[i]; dr = j + D[i];
}
else{
st = j - D[i] + 1; dr = j + D[i];
}
for ( ; st > 1 && dr < n && sir[st-1] == sir[dr+1] ; --st , ++dr , ++D[i] );
}
}
else{
if ( i & 1 ){
st = dr = j;
for ( ; st > 1 && dr < n && sir[st-1] == sir[dr+1] ; --st , ++dr , ++D[i] );
}
else{
st = j; dr = j+1; D[i] = 1;
if ( sir[st] == sir[dr] ){
for ( ; st > 1 && dr < n && sir[st-1] == sir[dr+1] ; --st , ++dr , ++D[i] );
}
else{
D[i] = 0;
}
}
}
}
for ( i = 1 ; i <= n + n ; ++i ){
D[i] = D[i]<<1;
D[i] += i&1;
}
for ( i = 1 ; i <= n + n ; ++i ){
if ( i & 1 ) nrpal += (D[i]+1)>>1;
else nrpal += (D[i]>>1);
}
fprintf(g,"%lld\n",nrpal);
fclose(f);
fclose(g);
return 0;
}