Cod sursa(job #2068831)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 18 noiembrie 2017 11:23:40
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 1000005

using namespace std;

char cuv[N];
int lp[2*N+1], nr=1, n;

void rezolvare()
{
    if(n==0)
        return;
    n=2*n+1;
    lp[1]=1;
    int c=1, r=2, iogl, exp, dif;
    for(int i=2;i<n;i++)
    {
        iogl=2*c-i;
        exp=0;
        dif=r-i;
        if(dif>0)
        {
            if(lp[iogl]<dif)
                lp[i]=lp[iogl];
            else
                if(lp[iogl]==dif && i==n-1)
                    lp[i]=lp[iogl];
            else
                if(lp[iogl]==dif && i<n-1)
                    lp[i]=lp[iogl], exp=1;
            else
                if(lp[iogl]>dif)
                    lp[i]=dif, exp=1;
        }
        else
            lp[i]=0, exp=1;
        if(exp)
            while((i+lp[i])<n && (i-lp[i])>0 && ((i+lp[i]+1)%2==0 || cuv[(i+lp[i]+1)/2]==cuv[(i-lp[i]-1)/2]))
                lp[i]++;
        if(i+lp[i]>r)
        {
            c=i;
            r=i+lp[i];
        }
        if(i%2==0)
            nr+=lp[i]/2;
        else
            nr+=(lp[i]+1)/2;
//        printf("%d ", lp[i]);
    }
}

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

    fgets(cuv, N, stdin);
    n=strlen(cuv)-1;
    cuv[n]='\0';
    rezolvare();
    printf("%d", nr);
    return 0;
}