Cod sursa(job #3250049)

Utilizator vlad7654vladimir manescu vlad7654 Data 19 octombrie 2024 09:50:11
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
vector<int> manacher_odd(string s) {
    int n=s.size();
    s="$"+s+"^";
    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 vector<int>(begin(p), end(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(){
    string s;
    fin>>s;
    vector<int> ans=manacher(s);
    int ans1=0;
    for(auto i:ans){
        ans1+=i/2;
    }
    fout<<ans1;
}