Cod sursa(job #3288654)

Utilizator cattyAninisCatrinel catty Data 23 martie 2025 14:55:02
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int i,lun,mj,p[2000005];
long long s;
string strax,st;
int main()
{
    ios_base::sync_with_stdio(false);
    in.tie(0);
    out.tie(0);
    in>>strax;
    st="**",lun=2;
    for(i=0;strax[i];++i)
        st+=strax[i],st+='*',lun+=2;
    mj=0;
    for(i=1;i<=lun;++i)
    {
        if(mj+p[mj]>=i)
        {
            p[i]=min(p[2*mj-i],mj+p[mj]-i);
            while(i+1+p[i]<=lun && i-1-p[i]>=1 && st[i+1+p[i]]==st[i-1-p[i]])
                ++p[i];
            if(i+p[i]>=mj+p[mj])
                mj=i;
        }
        else
        {
            p[i]=0;
            while(i+1+p[i]<=lun && i-1-p[i]>=1 && st[i+1+p[i]]==st[i-1-p[i]])
                ++p[i];
            mj=i;
        }
    }
    for(i=1;i<=lun;++i)
        s+=(p[i]+1)>>1;
        out<<s;
        return 0;
}