Cod sursa(job #3279857)

Utilizator andreea678Rusu Andreea-Cristina andreea678 Data 24 februarie 2025 16:20:08
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
vector<long long> p;
string s;
string s2; ///stringul prelucrat a#b#c#d#...f#
void manacher(string s){
    long long n=s2.length();
    p.assign(n,1);
    long long l=1, r=1;
    for(long long i=0; i<n; ++i){
        if(i<r){
            p[i]=max(1LL,min(r-i, p[l+r-i]));
        }
        while(i+p[i]<n && i-p[i]>=0 && s2[i+p[i]]==s2[i-p[i]]){
            p[i]++; ///expanding
        }
        if(i+p[i]>r){
            l=i-p[i]+1;
            r=i+p[i]-1;
        }
    }

}
int main()
{
    fin >> s;
    for(auto i : s){
        s2+=string("#")+i;
    }
    s2+="#";
    manacher(s2);
    int ans=0;
    for(auto i : p){
        ans+=i/2;
    }
    fout << ans;
    return 0;
}