Cod sursa(job #3263611)

Utilizator vladm98Munteanu Vlad vladm98 Data 15 decembrie 2024 15:26:47
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

int manacher[2000006];

int main()
{
    ifstream fin ("pscpld.in");
    ofstream fout ("pscpld.out");
    string s, initialS;
    fin >> initialS;
    s = "&&"; //pun de 2 ori caracterul special pentru ca vreau indexare de la 1.
    for (auto x : initialS) {
        s += x;
        s += "&";
    }

    int middle = 0;
    for (int i = 1; i < s.size(); ++i) {
        if (middle + manacher[middle] >= i) {
            manacher[i] = min(manacher[middle - (i - middle)], middle + manacher[middle] - i);
        }

        while (i + manacher[i] + 1 < s.size() and i - manacher[i] - 1 >= 1 and s[i + manacher[i] + 1] == s[i - manacher[i] - 1]) {
            manacher[i] += 1;
        }
        if (i + manacher[i] >= middle + manacher[middle]) {
            middle = i;
        }
    }

    long long answer = 0;
    for (int i = 1; i < s.size(); ++i) {
        answer += (manacher[i] + 1) / 2;
    }
    fout << answer;
    return 0;
}