Cod sursa(job #1304671)

Utilizator heracleRadu Muntean heracle Data 29 decembrie 2014 01:18:12
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
#include <cstring>

FILE* in=fopen("pscpld.in","r");
FILE* out=fopen("pscpld.out","w");

const int Q=1000007;

char v[2*Q],h[Q];
int p[2*Q];

int min(const int &a, const int &b)
{
    return a<b?a:b;
}

int n;

int main()
{
    fgets(h+1,Q,in);
    n=strlen(h+1);
    if(h[n]=='\n')
        n--;

    v[0]='#';

    int aux=0;

    for(int i=1; i<=n; i++)
    {
        v[++aux]=',';
        v[++aux]=h[i];
    }

    v[++aux]=',';
    v[++aux]='$';

    int max_right=0,max_center=0;
    long long rez=0;
    int d;

    for(int i=1; i<=2*n+1; i++)
    {
        d=0;
        if(i<max_right)
        {
            d=min(max_right-i,p[2*max_center-i]);
        }

        while(v[i-d-1]==v[i+d+1])
            d++;

        p[i]=d;
        rez+=(long long)(p[i]+1)/2;

        if(i+d>max_right)
        {
            max_right=i+d;
            max_center=i;
        }
    }
    fprintf(out,"%ld",rez);


    return 0;
}