Mai intai trebuie sa te autentifici.
Cod sursa(job #2522489)
Utilizator | Data | 12 ianuarie 2020 16:48:13 | |
---|---|---|---|
Problema | PScPld | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.08 kb |
#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 , dist ;
cin >> str ;
n = strlen ( str ) ;
for ( i = 0 ; i <= n ; ++ i )
str1 [ 2 * i + 1 ] = str [ i ] , str1 [ 2 * i ] = 0 ;
n *= 2 ;
for ( i = 1 ; i < n ; ++ i )
{
mxext = last + pld [ last ] ;
dist = 0 ;
if ( i <= mxext )
{
if ( pld [ 2 * last - i ] < mxext - i )
dist = pld [ 2 * last - i ] ;
else
dist = mxext - i ;
}
while ( i + dist < n && i - dist >= 1 && str1 [ i + dist ] == str1 [ i - dist ] )
++ dist ;
pld [ i ] = dist ;
-- dist ;
if ( i + dist > mxext )
last = i ;
ans += dist / 2 ;
}
cout << ans + n / 2 ;
return 0 ;
}