Cod sursa(job #2592201)

Utilizator andreic06Andrei Calota andreic06 Data 1 aprilie 2020 13:01:30
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb

///Tudy & Cal
#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 1000000;

int manacher[2 * NMAX + 3];
char s[2 * NMAX + 3];

int main() {
    FILE *fin = fopen( "pscpld.in", "r" );
    ofstream fout( "pscpld.out" );

    int i, n, length_so_far = 0, poz = 0, st, dr, length;

    s[0] = '&';
    s[1] = '#';

    n = 2;

    char ch;
    while ( ( ch = fgetc( fin ) ) != '\n' ) {
        s[n++] = ch;
        s[n++] = '#';
    }
    s[n++] = '%';

    long long palindrome = 0;
    for ( i = 2; i < n - 1; i ++ ) {
        if ( poz + length_so_far < i ) {
            st = i - 1;
            dr = i + 1;
            length = 0;
            while ( s[st] == s[dr] ) {
                st --;
                dr ++;
                length ++;
            }
        } else {
            manacher[i] = min ( poz + length_so_far - i, manacher[poz - ( i - poz )] );
            st = i - manacher[i] - 1;
            dr = i + manacher[i] + 1;
            length = manacher[i];
            while ( s[st] == s[dr] ) {
                st --;
                dr ++;
                length ++;
            }
        }
        manacher[i] = length;
        if ( manacher[i] + i >= length_so_far + poz ) {
            length_so_far = manacher[i];
            poz = i;
        }
        palindrome += manacher[i] / 2 + i % 2;
    }
    fout << palindrome;
    return 0;