Cod sursa(job #2883298)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 1 aprilie 2022 13:24:41
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

using ll = long long;
const int NMAX(1000005);
int lg[2 * NMAX];

inline void manacher(){
    string s;
    fin >> s;

    string ax1 = "$";
    for(auto it: s)
        ax1 += it, ax1 += "$";

    ll rez = 0;
    int dr = 0, cen = 0;
    for(int i = 1; i < (int)ax1.size(); ++i){
        if(i <= dr)
            lg[i] = min(dr - i + 1, lg[2 * cen - i]);
        while(i + lg[i] < (int)ax1.size() && i - lg[i] >= 0 && ax1[i - lg[i]] == ax1[i + lg[i]])
            ++lg[i];
        if(i + lg[i] - 1 > dr){
            dr = i + lg[i] - 1;
            cen = i;
        }
        if(i % 2)
            rez += ((lg[i] + 1) / 2);
        else rez += (lg[i]) / 2;
    }
    fout << rez << '\n';
}

int main()
{
    manacher();
    return 0;
}