Cod sursa(job #3305800)

Utilizator alexbaldovin20alex baldovin alexbaldovin20 Data 5 august 2025 10:49:17
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

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

int l[2000001];
int main() {
    string s;
    in>>s;
    string t="#";
    for(int i=0; i<s.size();i++) {
        t.push_back(s[i]);
        t.push_back('#');
    }
    s=t;
    int cen=0,mr=-1;
    long long ans=0;
    for(int i=0;i<s.size();i++) {
        if(cen<i and i<mr) {
            int mrr=2*cen-i;
            l[i]=min(l[mrr],mr-i);
        } else
            l[i]=0;
        while(i-l[i]-1>=0 and i+l[i]+1<s.size() and s[i-l[i]-1]==s[i+l[i]+1])
            l[i]++;
        if(i+l[i]>mr) {
            mr=i+l[i];
            cen=i;
        }
        ans+=l[i]/2+(s[i]!='#');
    }
    out<<ans<<"\n";
    return 0;
}