Cod sursa(job #2631021)

Utilizator vladm98Munteanu Vlad vladm98 Data 28 iunie 2020 15:56:26
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 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;
            }
        } else {
            manacher[i] = 0;
            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;
            }
            middle = i;
        }
    }

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