Cod sursa(job #1336129)

Utilizator wGEORGEWGeorge Cioti wGEORGEW Data 6 februarie 2015 18:56:37
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#define MAXN 1000000
char t[2*MAXN+3];
int p[2*MAXN+2];
int main(){
    long long ans;
    int n, c, r, i, j;
    char ch;
    FILE *fin, *fout;
    fin=fopen("pscpld.in", "r");
    fout=fopen("pscpld.out", "w");
    t[0]='^';
    n=1;
    ch=fgetc(fin);
    while(ch!='\n'){
        t[n++]='#';
        t[n++]=ch;
        ch=fgetc(fin);
    }
    t[n]='#';
    t[n+1]='$';
    ans=0;
    c=0;
    r=0;
    for(i=1; i<=n; i++){
        j=2*c-i;
        if(r>i){
            if(p[j]<=r-i){
                p[i]=p[j];
            }else{
                p[i]=r-i;
            }
        }
        while(t[i+p[i]+1]==t[i-p[i]-1]){
            p[i]++;
        }
        if(i+p[i]>r){
            c=i;
            r=i+p[i];
        }
        ans+=(p[i]+1)/2;
    }
    fprintf(fout, "%lld\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}