Cod sursa(job #2592175)

Utilizator Tudor06MusatTudor Tudor06 Data 1 aprilie 2020 12:36:42
Problema PScPld Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 1000000;

int manacher[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;
    string s = "&#";
    char ch;
    while ( isalpha( ch = fgetc( fin ) ) ) {
        s += ch;
        s += '#';
    }
    s += "%";
    n = s.size();
    for ( i = 2; i < n; i ++ ) {
        if ( poz + length_so_far < i ) {
            st = i - 1;
            dr = i + 1;
            length = 0;
            while ( s[st] == s[dr] ) {
                st --;
                dr ++;
                length ++;
            }
            manacher[i] = length;
        } else {
            manacher[i] = min( poz + length_so_far - i, manacher[poz - ( i - poz )] );
            st = i - manacher[i] - 1;
            dr = i + manacher[i] + 1;
            while ( s[st] == s[dr] ) {
                st --;
                dr ++;
                manacher[i] ++;
            }
        }
        if ( manacher[i] + i >= length_so_far + poz ) {
            length_so_far = manacher[i];
            poz = i;
        }
    }
    long long palindrome = 0;
    for ( i = 2; i < n; i ++ ) {
        if ( s[i] != '#' ) {
            palindrome += manacher[i] / 2;
        } else {
            palindrome += manacher[i] / 2 + 1;
        }
    }
    fout << palindrome;
    return 0;
}