Cod sursa(job #3288651)

Utilizator cattyAninisCatrinel catty Data 23 martie 2025 14:41:45
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int i,lun,mj,p[2000005],s;
string strax,st;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.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-1],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;
}