Cod sursa(job #1255712)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 5 noiembrie 2014 02:42:26
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<cstdio>
#include<cstring>
int i,j,l,v[2001000],c,r,a;
long long nr;
char s[2001000],x[2001000];
FILE *f,*g;
int minim(int a,int b){
    if(a<b)
        return a;
    return b;
}
int main(){
    f=fopen("pscpld.in","r");
    g=fopen("pscpld.out","w");
    fscanf(f,"%s",s);
    l=strlen(s);
    for(i=1;i<=l;i++){
        x[2*i-1]='#';
        x[2*i]=s[i-1];
    }
    l=l*2+1;
    x[l]='#';
    x[l+1]=0;
    for(i=2;i<l;i++){
        a=2*c-i;
        if(r>i)
            v[i]=minim(r-i,v[a]);
        else
            v[i]=0;
        while(i-v[i]>1&&x[i-v[i]-1]==x[i+v[i]+1])
            v[i]++;
        if(i+v[i]>r){
            c=i;
            r=i+v[i];
        }
    }
    for(i=1;i<=l;i++){
        if(x[i]=='#')
            nr+=v[i]/2;
        else
            nr+=v[i]/2+1;
    }
    fprintf(g,"%lld",nr);
    fclose(f);
    fclose(g);
    return 0;
}