Cod sursa(job #61524)

Utilizator ZeusCatalin Tiseanu Zeus Data 19 mai 2007 18:34:25
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 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 )
{
     int i, j, k;
     
     Rad[1] = !h, i = 2, j = Rad[1];
     
     for( ; i <= N; )
     {
          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 )
                ++k;
          j = max( j - k, 0 );
          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 );
    
    cout << baga_mare( 0 ) + baga_mare( 1 ) << endl;
    
    return 0;    
}