Cod sursa(job #2539203)

Utilizator Vlad.Vlad Cristian Vlad. Data 5 februarie 2020 18:56:13
Problema PScPld Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <iostream>
#define NMAX 2 * 1000000 + 5
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char str[NMAX];
int N, L[NMAX];
void read() {
    char c;
    int i = 0;
    fin.get(c);
    while (c != '\n') {
        if (i % 2 == 0) {
            str[i++] = '!';
        }
        else {
            str[i++] = c;
            fin.get(c);
        }
    }
    str[i] = '!';
    N = i;
}
void manacher() {
    int right = 2, center = 1, simi, dist;
    bool expand;
    L[0] = L[N] = 0;
    L[1] = 1;
    for (int i = 2; i <= N; ++i) {
        simi = 2 * center - i;
        bool expand = false;
        dist = right - i;
        if (dist > 0) {
            if (L[simi] < dist || i == N - 1) {
                L[i] = L[simi];
            }
            else {
                L[i] = min(L[simi], dist);
                expand = true;
            }
        }
        else {
            L[i] = 0;
            expand = true;
        }
        if (expand) {
            while ((i + L[i]) < N && (i - L[i]) > 0 && str[i + L[i] + 1] == str[i - L[i] - 1]) {
                L[i]++;
            }
        }
        if (i + L[i] > right) {
            center = i;
            right = i + L[i];
        }
    }
}
int main()
{
    read();
    manacher();
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += (L[i] / 2);
        if (i & 1) {
            sum++;
        }
    }
    fout << sum << "\n";
    return 0;
}