Cod sursa(job #2909350)

Utilizator mihneazzzMacovei Daniel mihneazzz Data 13 iunie 2022 00:20:11
Problema PScPld Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 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;
}