Pagini recente » Cod sursa (job #1385617) | Cod sursa (job #192113) | Cod sursa (job #2579767) | Cod sursa (job #2181671) | Cod sursa (job #61539)
Cod sursa(job #61539)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int N, Rad[1001001];
char text[1001001];
long long baga_mare( int h )
{
// printf("%s\n", text + 1 );
int i, j, k;
if( !h )
{ j = Rad[1] = 1; }
else
{ j = Rad[1] = ( text[1] == text[2] ); }
i = 2;
for( ; i <= N; )
{
// cout << " ->>> " << i << endl;
while( i - j >= 1 && i + j + h <= N && text[ i - j ] == text[ i + j + h ] )
++j;
Rad[i] = j;
k = 1;
while( i - k >= 1 && i + k <= N && Rad[i] - k != Rad[i-k] && Rad[i] > k )
Rad[ i + k ] = min( Rad[i] - k, Rad[ i - k ] ),
++k;
j = max( j - k, (int)!h );
i += k;
}
// for( int i = 1; i <= N; i++ )
// printf("Rad[%d] = %d\n", i, Rad[i] );
long long res(0);
for( int i = 1; i <= N; ++i )
res += ( long long )( Rad[i] );
return res;
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
long long res = 0;
scanf("%s", text + 1 );
N = strlen( text + 1 );
if( N == 1 )
cout << 1 << endl;
else
cout << baga_mare( 0 ) + baga_mare( 1 ) << endl;
return 0;
}