Cod sursa(job #2068883)

Utilizator patricia.predaPatricia Preda patricia.preda Data 18 noiembrie 2017 11:31:54
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char cuv[2000010];
long long lp[2000010];
int centru,dr,lgmax,contor,lg,suma=1;

int mini(int a,int b)
{
    if(a<b)
        return a;
    return b;
}

void citire()
{
    cin.getline(cuv,1000005);
    lg=strlen(cuv);
    contor=lg;
    lg=2*lg+1;
}

void cel_mai_lung()
{
    lp[1]=1;
    if(lg==0)
        return;
    for(int i=2; i<lg; i++)
    {
        if(dr-i>0)
            lp[i]=mini(lp[2*centru-i],dr-i);
        while(((i+lp[i])<lg&&(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])%2!=0)
                contor++;
        }
        if(lp[i]>lgmax)
        {
            lgmax=lp[i];
            //maxLPSCenterPosition = i;
        }
        if (i+lp[i]>dr)
        {
            centru=i;
            dr=i+lp[i];
        }
        if(i%2==0)
            suma+=(lp[i])/2;
        else
            suma+=(lp[i]+1)/2;
    }
}

int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    citire();
    cel_mai_lung();
    cout<<suma;
    return 0;
}