Cod sursa(job #2841458)

Utilizator betybety bety bety Data 29 ianuarie 2022 19:15:52
Problema PScPld Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
long long manacher(string s)
{
    string a="@#";
    for(char c:s)
        a+=c+string("#");
    a+='$';
    int l=0,r=-1;
    int n=a.size()-2;
    vector<int> p(n+2);
    for(int i=1;i<=n;++i)
    {
        p[i]=max(0,min(r-i,p[l+r-i]));
        while(a[i-p[i]]==a[i+p[i]])
            ++p[i];
        if(i+p[i]>r)
            l=i-p[i],r=i+p[i];
    }
    long long ans=0;
    for(int i=2;i<p.size()-2;++i)
        ans+=p[i]/2;
    return ans;
}
string s;
int main()
{
    ios_base::sync_with_stdio(false);
    in.tie(0),out.tie(0);
    in>>s;
    out<<manacher(s)<<'\n';
    return 0;
}