Pagini recente » Cod sursa (job #1248304) | Cod sursa (job #1044204) | Cod sursa (job #2804826) | Cod sursa (job #26636) | Cod sursa (job #934694)
Cod sursa(job #934694)
#include<stdio.h>
#include<cstring>
#define maxn 1000005
FILE*f=fopen("pscpld.in","r");
FILE*g=fopen("pscpld.out","w");
int n;
int lung[maxn];
char sir[maxn];
inline int min ( const int &a , const int &b ){
return a <= b ? a : b;
}
int main () {
fscanf(f,"%s",sir+1); n = strlen(sir+1);
int st = 0,dr = 0;
for ( int i = 1 ; i <= n ; ++i ){
if ( i <= dr ){
lung[i] = min(lung[st+dr-i],dr-i+1);
int p = i-lung[i]+1,u = i+lung[i]-1;
while ( p > 1 && u < n && sir[p-1] == sir[u+1] ){
++lung[i];
--p; ++u;
}
if ( u > dr ){
st = p,dr = u;
}
}
else{
lung[i] = 1;
int p = i,u = i;
while ( p > 1 && u < n && sir[p-1] == sir[u+1] ){
++lung[i];
--p; ++u;
}
st = p,dr = u;
}
}
long long sol = 0;
for ( int i = 1 ; i <= n ; ++i ){
sol += lung[i];
}
st = dr = 0;
for ( int i = 1 ; i < n ; ++i ){
if ( sir[i] != sir[i+1] ){
lung[i] = 0;
continue ;
}
if ( i < dr ){
lung[i] = min(lung[st+dr-i-1],dr-i);
int p = i-lung[i]+1,u = i+lung[i];
while ( p > 1 && u < n && sir[p-1] == sir[u+1] ){
++lung[i];
--p; ++u;
}
if ( u > dr ){
st = p,dr = u;
}
}
else{
lung[i] = 1;
int p = i,u = i+1;
while ( p > 1 && u < n && sir[p-1] == sir[u+1] ){
++lung[i];
--p; ++u;
}
st = p,dr = u;
}
}
for ( int i = 1 ; i < n ; ++i ){
sol += lung[i];
}
fprintf(g,"%lld\n",sol);
fclose(f);
fclose(g);
return 0;
}