Cod sursa(job #3293512)

Utilizator Bubu_OrangeAlin Lupau Bubu_Orange Data 11 aprilie 2025 20:52:11
Problema PScPld Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<bits/stdc++.h>

using namespace std;

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

int p[2000005];

void manacher_odd(string s){
    int n=s.size();
    s='$'+s+'^';
    int l=0, 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];
        }
    }
}

int main()
{
    string s, t="";
    in>>s;
    for(auto c:s){
        t=t+'#'+c;
    }
    t+='#';
    manacher_odd(t);
    long long sol=0;
    for(int i=1; i<=t.size(); i++){
        p[i]/=2;
        sol+=p[i];
    }
    out<<sol;
    return 0;
}