Cod sursa(job #2719295)

Utilizator vladm98Munteanu Vlad vladm98 Data 9 martie 2021 19:11:00
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

int manacher[2000005];
string s;

int main() {
    ifstream fin ("pscpld.in");
    ofstream fout ("pscpld.out");
    ios::sync_with_stdio(false);
    fin.tie(nullptr);
    int middle = 0;
    string input;
    fin >> input;
    s = "$";
    s += "$";
    for (auto x : input) {
        s += x;
        s += "$";
    }
    long long ans = 0;
    for (int i = 1; i < s.size(); ++i) {
        if (i > middle + manacher[middle]) {
            manacher[i] = 0;
        } else {
            manacher[i] = min(manacher[2 * middle - i], middle + manacher[middle] - i);
        }
        while (i - manacher[i] - 1 >= 1 and i + manacher[i] + 1 < s.size() and s[i - manacher[i] - 1] == s[i + manacher[i] + 1]) {
            manacher[i] += 1;
        }
        if (middle + manacher[middle] < i + manacher[i]) {
            middle = i;
        }
        ans += (manacher[i] + 1) / 2;
    }
    fout << ans;
    return 0;
}