Cod sursa(job #2376835)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 8 martie 2019 18:02:42
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>

#define llg long long

#define MAXN 1000005

int N, DP[2*MAXN];
std::string S, Input;

void Manacher() {
    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] < N && S[i+DP[i]+1] == S[i-DP[i]-1])
            ++ DP[i];
        if (DP[i] + i > Right)
            Center = i, Right = i + DP[i];
    }
}

std::ifstream In ("pscpld.in");
std::ofstream Out("pscpld.out");

void Citire() {
    In >> Input;
    N = Input.size();
    S += "$#";
    for (int i=0; i<N; ++i)
        S += Input[i], S += "#";
    S += "$";
}

void Rezolvare() {
    Manacher();

    llg Ans = 0;
    for (int i=1; i<S.size(); ++i)
        Ans += 1LL * (DP[i] / 2 + (DP[i]&1));
    Out << Ans << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}