Cod sursa(job #1880204)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 15 februarie 2017 16:54:23
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define NMax 1000005

using namespace std;

char s[NMax];
int LPS[NMax];

void Read()
{
    scanf("%s", &s);
}

void Solve()
{
    int C,R,N=strlen(s);
    int expand, lmax, cmax,ii,ok;
    LPS[0]=0;
    LPS[1]=1;
    C=1;
    R=2;
    N=2*N+1;
    lmax=1;
    cmax=1;

    for(int i=2; i<=N; ++i)
    {
        ii=2*C-i;
        expand=0;

        if(R<=i)
        {
            LPS[i]=0;
            expand=1;
        }

        else
        {
            if(LPS[ii]<R-i)
                LPS[i]=LPS[ii];

            else
            {
                LPS[i]=min(LPS[ii], R-i);
                expand=1;
            }
        }

        if(expand)
        {
            ok=1;
            while(i-LPS[i]>0 && ok ==1 && i+LPS[i]< N )
                if((i-LPS[i]-1)%2==0)
                    LPS[i]=LPS[i]+1;

                else if(s[i-LPS[i]-1]==s[i+LPS[i]+1])
                    LPS[i]=LPS[i]+1;
                else
                    ok=0;
        }

        if(lmax<LPS[i])
        {
            lmax=LPS[i];
            cmax=i;
        }

        if(i+LPS[i]>R)
        {
            R=i+LPS[i];
            C=i;
        }
    }

    long long S=0;

    for(int i=1; i<=N-2; ++i)
    {
        if(LPS[i]%2==0)
            S+=LPS[i]/2;

        else
            S+=LPS[i]/2+1;
    }

    printf("%lld", S);

}

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);

    Read();
    Solve();
    return 0;
}