Mai intai trebuie sa te autentifici.
Cod sursa(job #2522453)
Utilizator | Data | 12 ianuarie 2020 16:03:44 | |
---|---|---|---|
Problema | PScPld | Scor | 30 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.26 kb |
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
const int NMAX = 1e6 ;
char str [ NMAX + 5 ] ;
char str1 [ 2 * NMAX + 5 ] ;
int pld [ 2 * NMAX + 5 ] ;
int main ()
{
FILE * f ;
f = fopen ( "pscpld.in" , "r" ) ;
freopen ( "pscpld.out" , "w" , stdout ) ;
int n , i , last = 0 , mxext = 0 , cnt , ans = 0 ;
fread ( str , 1 , NMAX , f ) ;
n = strlen ( str ) ; -- n ;
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 ;
}
for ( i = 1 ; i < 2 * n ; ++ i )
{
/*if ( str1 [ i ] == 0 )
str1 [ i ] = '*' ;
printf ( "%2d : %d %c\n" , i , pld [ i ] , str1 [ i ] ) ;*/
ans += ( pld [ i ] + 1 ) / 2 ;
}
printf ( "%d" , ans + n ) ;
return 0 ;
}