Cod sursa(job #2016418)

Utilizator robx12lnLinca Robert robx12ln Data 29 august 2017 13:05:42
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<fstream>
#include<cstring>
#define DIM 2000005
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int n, Long_pal[DIM], poz, R, C;
long long sol = 0;
char s[DIM / 2], v[DIM];
int main(){
    fin >> s + 1;
    n = strlen( s + 1 );
    n = n * 2 + 1;
    poz = 1;
    for( int i = 1; i <= n; i++ ){
        if( i % 2 == 0 )
            v[i] = s[poz++];
        else
            v[i] = '#';
    }
    v[0] = '0';
    v[n + 1] = '1';
    C = R = 0;
    for( int i = 1; i <= n; i++ ){
        int mirr_poz = 2 * C - i;
        if( i < R )
            Long_pal[i] = min( R - i, Long_pal[mirr_poz] );
        while( v[ i - Long_pal[i] - 1 ] == v[ i + Long_pal[i] + 1 ] )
            Long_pal[i]++;
        if( i + Long_pal[i] > R ){
            R = i + Long_pal[i];
            C = i;
        }
        sol += (Long_pal[i] + 1) / 2;
    }
    fout << sol << "\n";
    return 0;
}