Cod sursa(job #2719272)

Utilizator vladm98Munteanu Vlad vladm98 Data 9 martie 2021 18:57:59
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;
int manacher[2000005];

int main()
{
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");

    string s, source = "&";
    int cnt = 0, a = 0, n;
    fin >> s;

    n = s.size() * 2 + 1;

    for (int i = 1; i <= n; ++i) {
        if (i % 2 != 0) {
            source += "$";
        } else {
            source += s.at(a);
            a += 1;
        }
    }

    int j = -1, pal_j = -1;

    for (int i = 1; i <= n; ++i) {
        manacher[i] = 1;
    }

    for (int i = 1; i <= n; ++i) {
        if (i > j + (pal_j - 1) / 2) {
            int m = i + 1;
            while (source[m] == source[2 * i - m]) {
                manacher[i] += 2;
                m += 1;
            }
            if (manacher[i] > pal_j) {
                pal_j = manacher[i];
                j = i;
            }
        } else if (i + (manacher[2 * j - i] - 1) / 2 < j + (pal_j - 1) / 2) {
            manacher[i] = manacher[2 * j - i];
        } else {
            manacher[i] = manacher[2 * j - i];
            int x = (manacher[i] - 1) / 2;
            int p = i + x + 1;
            while (source[p] == source[2 * i - p]) {
                manacher[i] += 2;
                p += 1;
            }
            if (manacher[i] > pal_j) {
                pal_j = manacher[i];
                j = i;
            }
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += (manacher[i] / 2 + 1) / 2;
    }
    fout << ans;

    return 0;

}