Cod sursa(job #2910922)

Utilizator mihneazzzMacovei Daniel mihneazzz Data 25 iunie 2022 20:03:57
Problema PScPld Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

#define N 1000005

using namespace std;

ifstream fin("pscpld.in");

ofstream fout("pscpld.out");



long long ans;

string s;

vector<int> manacher_odd(string s) {

    int n = s.size();

    vector<int> p(n + 2);

    int l = 1, r = 1;

    for(int i = 1; i <= n; i++) {

        p[i] = max(0, min(r - i, p[l + (r - i)]));

        while(s[i - p[i]] == s[i + p[i]]) {

            p[i]++;

        }

        if(i + p[i] > r) {

            l = i - p[i], r = i + p[i];

        }

    }

    return p;

}

vector<int> manacher(string s) {

    string t="";

    for(auto c: s) {

        t += string("#") + c;

    }

    auto res = manacher_odd(t + "#");

    return vector<int>(begin(res) + 1, end(res) - 1);

}



int main()

{

    fin>>s;

    vector<int>p=manacher(s);

    for(auto x:p) ans+=x/2;

    fout<<ans;

    return 0;

}