Pagini recente » Cod sursa (job #2748490) | Cod sursa (job #448905) | Cod sursa (job #2259820) | Cod sursa (job #3188346) | Cod sursa (job #479804)
Cod sursa(job #479804)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define Nmax 1000010
using namespace std;
long long L1[Nmax],L2[Nmax],n,i,sol,pal;
char v[Nmax];
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",v+1);
pal = 1 ;
n = strlen(v+1);
sol = n ;
for( i = 1 ; i <= n ; i++ )
{
if ( i < pal + L1[pal] )
L1[i] = min( L1[ 2*pal - i ] , pal + L1[pal] - i ) ;
if ( i + L1[i] >= pal + L1[pal] )
{
pal = i ;
while ( i - L1[i] >= 1 && i + L1[i] + 1 <= n && v[ i - L1[i] ] == v[ i + L1[i] + 1 ] )
L1[i]++;
}
}
for( i = 1 ; i <= n ; i++ )
sol += L1[i];
pal = 1 ;
for( i = 1 ; i <= n ; i++ )
{
if ( i < pal + L2[pal] )
L2[i] = min( L2[ 2*pal - i ] , pal + L2[pal] - i ) ;
if ( i + L2[i] >= pal + L2[pal] )
{
pal = i ;
while ( i - L2[i] - 1 >= 1 && i + L2[i] + 1 <= n && v[ i - L2[i] - 1 ] == v[ i + L2[i] + 1 ] )
L2[i]++;
}
}
for( i = 1 ; i <= n ; i++ )
sol += L2[i];
printf("%lld",sol);
return 0;
}