Cod sursa(job #2517925)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 4 ianuarie 2020 15:21:56
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

std::ifstream input ("pscpld.in");
std::ofstream output("pscpld.out");

class ManacherCalculator {
public:
    ManacherCalculator(std::string string) {
        DP.resize(2*string.size() + 3);
        src = string;
        buildData();
        runAlgorithm();
    }
    int even(int idx) { return DP[2*idx+2]; }
    int odd (int idx) { return DP[2*idx+1]; }
private:
    std::vector <int> DP;
    std::string src;
    std::string S;
    void buildData() {
        S += "$#";
        for (int i=0; i<src.size(); ++i) S += src[i], S += "#";
        S += "$";
    }
    void runAlgorithm() {
        int center = 0, right = 0, mirror;
        for (int i=1; i<S.size()-1; ++i) {
            mirror = 2*center - i;
            if (i < right) DP[i] = std::min(DP[mirror], right - i);
            while (DP[i] < src.size() && S[i+DP[i]+1] == S[i-DP[i]-1]) ++ DP[i];
            if (DP[i] + i > right) center = i, right = i + DP[i];
        }
    }
};

int main()
{
    int N;
    std::string str;
    input >> str;
    N = str.size();

    ManacherCalculator calc(str);
    long long ans = 0;
    for (int i=0; i<N;   ++i) ans += 1ll * ((calc.odd(i)+1)/2);
    for (int i=0; i<N+1; ++i) ans += 1ll * ((calc.even(i)+1)/2);
    output << ans;

    return 0;
}