Cod sursa(job #2068972)

Utilizator patricia.predaPatricia Preda patricia.preda Data 18 noiembrie 2017 11:41:46
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
/**#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

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

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++)
    {
        og=2*centru-i;
        dif=dr-i;
        if(dr-i>0)
            lp[i]=min(lp[og],dif);
        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]>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;
}
*/
#include <iostream>
#include <fstream>
#include <cstring>
#define X 2000001

using namespace std;
int LP[X],n,i,r=2,c=1,oglinda,dif;
char a[X];
int main()
{
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");
    fin.get(a,X);
    n=strlen(a);
    n=2*n+1;
    LP[0]=0;
    LP[1]=1;
    long long s=1;
    for(int i=2;i<=n;i++)
    {
        oglinda=2*c-i;
        dif=r-i;
        if(dif>0)
            LP[i]=min(LP[oglinda],dif);
         while ( ((i + LP[i]) < n && (i - LP[i]) > 0) && ( ((i + LP[i] + 1) % 2 == 0) || (a[(i + LP[i] + 1)/2] == a[(i - LP[i] - 1)/2] )))
        {
            LP[i]++;
        }
        if (i + LP[i] > r)
        {
            c = i;
            r = i + LP[i];
        }
            if(LP[i]%2==1)
                s=s+LP[i]/2+1;
            else
                s=s+LP[i]/2;
    }
            fout<<s;
    return 0;
}