Pagini recente » Cod sursa (job #1118905) | Cod sursa (job #1771877) | Cod sursa (job #2978691) | Cod sursa (job #1432640) | Cod sursa (job #1315158)
/*
* Code by Spiromanul
*/
#include <fstream>
#include <cstring>
const char IN [ ] = "pscpld.in" ;
const char OUT [ ] = "pscpld.out" ;
const int MAX = 1110111 ;
using namespace std;
ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;
char sir [ MAX << 1 ] ;
char S [ MAX ] ;
int pali [ MAX << 1 ] , n ;
int main ( )
{
fin >> ( S + 1 ) ;
int l = strlen ( S + 1 ) ;
sir [ n ] = '$' ;
for ( int i = 1 ; i <= l ; ++ i )
{
++ n ;
sir [ n ] = S [ i ] ;
++ n ;
sir [ n ] = '$' ;
}
sir [ n + 1 ] = '@' ;
pali [ 0 ] = 1 ;
pali [ 1 ] = 1 ;
int centru = 1 ;
int R = 1 ;
for ( int i = 2 ; i < n ; ++ i )
{
pali [ i ] = ( R > i ) ? min ( pali [ 2 * centru - i ] , R - i ) : 0 ;
while ( sir [ i - pali [ i ] - 1 ] == sir [ i + pali [ i ] + 1 ] )
++ pali [ i ] ;
if ( i + pali [ i ] > R )
{
R = i + pali [ i ] ;
centru = i ;
}
}
long long CET = 0 ;
for ( int i = 1 ; i <= n ; ++ i )
CET += ( long long ) ( pali [ i ] + 1 ) >> 1 ;
fout << CET << '\n' ;
return 0;
}