Cod sursa(job #803326)

Utilizator mihai995mihai995 mihai995 Data 27 octombrie 2012 13:27:43
Problema PScPld Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <cstring>
using namespace std;

const int N = 2000005;
int pali[N];
char s[N];

ifstream in("pscpld.in");
ofstream out("pscpld.out");

void stretch(char* s){
    for (int i = 2 * strlen(s + 1) - 1 ; i ; i--)
        if (i & 1)
            s[i] = s[ (i + 1) >> 1];
        else
            s[i] = '#';
}

void manacher(char* s){
    int best = 0;

    for (int i = 1 ; s[i] ; i++){
        if (best + pali[best] >= i)
            pali[i] = min(best + pali[best], i + pali[2 * i - best]) - i;

        while (pali[i] < i && s[ i - pali[i] - 1 ] == s[ i + pali[i] + 1 ] )
            pali[i]++;

        best = best + pali[best] >= i + pali[i] ? best : i;
    }
}

int main(){
    in.getline(s + 1, N);

    stretch(s);

    manacher(s);

    int rez = 0;

    for (int i = 1 ; s[i] ; i++)
        rez += (pali[i] + 1 + (i & 1)) >> 1;

    out << rez << "\n";

    return 0;
}