Cod sursa(job #2715730)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 4 martie 2021 09:54:02
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <string>

using namespace std;

ifstream cin("pscpld.in");
ofstream cout("pscpld.out");

const int NMAX = 1e6;

string s;
int manacher[2 * NMAX + 5];
long long ans;

void Manacher() {

    int drMax = -1, posDrMax = -1;
    for(int i = 0; i < (int)s.size(); i++) {
        if(i > drMax) {
            int st = i - 1, dr = i + 1;
            while(st >= 0 && dr < (int)s.size() && s[st] == s[dr]) {
                st--, dr++;
            }

            st++, dr--;

            manacher[i] = dr - i;

            drMax = dr;
            posDrMax = i;

        } else {
            if(i + manacher[2 * posDrMax - i] < drMax) {
                manacher[i] = manacher[2 * posDrMax - i];
            } else {
                int st = 2 * i - drMax - 1, dr = drMax + 1;

                while(st >= 0 && dr < (int)s.size() && s[st] == s[dr]) {
                    st--, dr++;
                }

                st++, dr--;

                manacher[i] = dr - i;

                drMax = dr;
                posDrMax = i;
            }
        }
    }

    for(int i = 0; i < (int)s.size(); i++) {
        if(i % 2 == 0) {
            ///'*'
            ans += (manacher[i] + 1) / 2;
        } else {
            ///'a'-'z'
            ans += (manacher[i] + 2) / 2;
        }
    }
}

int main() {
    string aux;
    cin >> aux;

    s += '*';
    for(char c : aux) {
        s += c;
        s += '*';
    }

    Manacher();

    cout << ans << '\n';
    return 0;
}