Pagini recente » Cod sursa (job #245564) | Cod sursa (job #171506) | Profil Andrei-27 | Cod sursa (job #33540) | Cod sursa (job #2022197)
/**
* Code by Patrick Sava
* "Spiru Haret" National College of Bucharest
**/
# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"
const char IN [ ] = "pscpld.in" ;
const char OUT [ ] = "pscpld.out" ;
using namespace std ;
# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )
ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;
const int MAX = 2e6 + 14 ;
char sir [ MAX >> 1 ] ;
char M [ MAX ] ;
int pali [ MAX ] ;
int main()
{
cin >> ( sir + 1 ) ;
int l = strlen ( sir + 1 ) ;
int n = 0 ;
FORN ( i , 1 , l )
{
++ n ;
M [ n ] = sir [ i ] ;
++ n ;
M [ n ] = '#' ;
}
-- n ;
int center = 1 ;
int R = 0 ;
pali [ 1 ] = 0 ;
FORN ( i , 1 , n )
{
if ( i > center + R ) {
while ( i - pali [ i ] >= 1 and i + pali [ i ] <= n and M [ i - pali [ i ] ] == M [ i + pali [ i ] ] )
++ pali [ i ] ;
}
else {
//int rr = i - center ;
//int sim = center - rr ;
int sim = 2 * center - i ;
//cout << sim << ' ' << pali [ sim ] << '\n' ;
pali [ i ] = min ( pali [ sim ] , center + R - i ) ;
while ( i - pali [ i ] >= 1 and i + pali [ i ] <= n and M [ i - pali [ i ] ] == M [ i + pali [ i ] ] ) {
++ pali [ i ] ;
assert (pali [sim] >= center + R - i) ;
}
}
if ( i + pali [ i ] - 1 > center + R ) {
center = i ;
R = pali [ i ] - 1 ;
}
//cout << pali [ i ] << ' ' ;
}
//cout << endl ;
long long result = 0 ;
FORN ( i , 1 , n ) {
if ( M [ i ] != '#' )
result = result + ( pali [ i ] + 1 ) / 2 ;
else
result = result + ( pali [ i ] ) / 2 ;
//cout << M [ i ] << ' ' ;
}
//cout << endl ;
cout << result << '\n' ;
return 0 ;
}