Pagini recente » Cod sursa (job #2853691) | Cod sursa (job #1274870) | Cod sursa (job #2157557) | Cod sursa (job #2265817) | Cod sursa (job #2522461)
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;
const int NMAX = 1e6 ;
char str [ NMAX + 5 ] ;
char str1 [ 2 * NMAX + 5 ] ;
long long pld [ 2 * NMAX + 5 ] ;
int main ()
{
ifstream cin ( "pscpld.in" ) ;
ofstream cout ( "pscpld.out" ) ;
long long n , i , last = 0 , mxext = 0 , cnt , ans = 0 ;
cin >> str ;
n = strlen ( str ) ;
for ( i = 0 ; i <= n ; ++ i )
str1 [ 2 * i + 1 ] = str [ i ] , str1 [ 2 * i ] = 0 ;
for ( i = 1 ; i < 2 * n ; ++ i )
{
mxext = last + pld [ last ] ;
if ( i <= mxext )
pld [ i ] = min ( pld [ last - ( i - last ) ] , mxext - i ) ;
while ( i + pld [ i ] < 2 * n && i - pld [ i ] >= 1 && str1 [ i + pld [ i ] ] == str1 [ i - pld [ i ] ] )
++ pld [ i ] ;
-- pld [ i ] ;
if ( pld [ i ] && str1 [ i + pld [ i ] ] == 0 )
-- pld [ i ] ;
if ( i + pld [ i ] > mxext )
last = i ;
ans += ( pld [ i ] + 1 ) / 2 ;
}
cout << ans + n ;
return 0 ;
}