Cod sursa(job #61539)

Utilizator ZeusCatalin Tiseanu Zeus Data 19 mai 2007 18:54:11
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb

#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;    
}