Cod sursa(job #2845381)

Utilizator loraclorac lorac lorac Data 7 februarie 2022 19:17:21
Problema PScPld Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int lim=1e6+5;
int d[lim];
string a,s;
int main()
{
    ios_base::sync_with_stdio(false);
    in.tie(0),out.tie(0);
    in>>a;
    s="@#";
    for(char c:a)
        s+=c,s+='#';
    s+='$';
    int l=0,r=-1;
    int n=s.size()-2;
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        d[i]=max(0,min(r-i,d[l+r-i]));
        while(s[i-d[i]]==s[i+d[i]])
            ++d[i];
        if(i+d[i]>r)
            l=i-d[i],r=i+d[i];
        if(i!=1 and i!=n)
            ans+=1LL*d[i]/2;
    }
    out<<ans<<'\n';
    return 0;
}