Cod sursa(job #2526561)

Utilizator dianaICHBghita diana dianaICHB Data 18 ianuarie 2020 19:57:38
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <cstring>

using namespace std;
char v[1000005],w[2000010];
int p[2000010];
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    int i,n,m=0,c,st,dr,maxx=0;
    long long int sol=0;
    fgets(v+1,1000005,stdin);
    n=strlen(v+1)-1;
    for(i=1; i<=n; i++)
    {
        w[++m]=v[i];
        p[m++]=1;
        //m=m+2;
    }
    for(i=1;i<=m-1;i++)
    {
        if(i<=maxx)
        {
            if (maxx-i+1<=p[2*c-i])
                p[i]=maxx-i+1;
            else
                p[i]=p[2*c-i];
        }
        st=i;
        dr=i;
        st--;
        dr++;
        st=st-p[i];
        dr=dr+p[i];
        while(st>=1&&dr<=m&&w[st]==w[dr])
        {
            p[i]=p[i]+2;
            st=st-2;
            dr=dr+2;
        }
        dr=dr-2;
        if(dr>maxx)
        {
            maxx=dr;
            c=i;
        }
        sol=sol+(p[i]+1)/2;
    }
    printf("%lld\n",sol);
    return 0;
}