Cod sursa(job #1880265)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 15 februarie 2017 17:28:15
Problema PScPld Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define NMax 1000010

using namespace std;

char s[NMax];
int LPS[2*NMax+2], N;

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

    N=strlen(s);

}

void Solve()
{
    int C,R;
    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)
    {
        int ii=2*C-1;

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

        else
            LPS[i]=0;

        while((i - LPS[i]-1 >= 0  && i + LPS[i] + 1 <= N) && ((s[(i-LPS[i]-1)/2] == s[(i + LPS[i]+1)/2]) || ((1+LPS[i]+i)%2 == 0 )))
            LPS[i]++;



        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;
}