Cod sursa(job #1491882)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 26 septembrie 2015 12:35:16
Problema Abc2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXCUV 50000
#define MOD 666013
char *buffer;
unsigned int v[MAXCUV+1];
int ind[MOD+1],next[MAXCUV+1],conb;
inline void blanc(int lSize){
    while(conb<lSize&&(buffer[conb]<'a'||buffer[conb]>'c'))
        conb++;
}
inline int cauta(int mod,unsigned int x){
    int poz=ind[mod];
    while(poz>0){
        if(v[poz]==x)
            poz=-1;
        else
            poz=next[poz];
    }
    return (poz==-1);
}
int main(){
    FILE*fi,*fout;
    int con,m,n,l,i,lSize,x;
    unsigned int nr,p3;
    fi=fopen("abc2.in" ,"rb");
    fout=fopen("abc2.out" ,"w");
    fseek(fi,0,SEEK_END);
    lSize=ftell(fi);
    rewind(fi);
    buffer=(char*) malloc(sizeof(char)*lSize);
    fread(buffer,1,lSize,fi);
    n=0;
    while(buffer[n]>='a'&&buffer[n]<='c')
        n++;
    conb=n;
    blanc(lSize);
    m=1;
    while(conb<lSize){
        l=0;
        while(conb<lSize&&buffer[conb]>='a'&&buffer[conb]<='c'){
            v[m]=v[m]*3+buffer[conb]-'a';
            l++;
            conb++;
        }
        blanc(lSize);
        next[m]=ind[v[m]%MOD];
        ind[v[m]%MOD]=m;
        m++;
    }
    p3=1;
    for(i=0;i<l-1;i++)
        p3*=3;
    nr=0;
    for(i=0;i<l;i++)
         nr=nr*3+buffer[i]-'a';
    con=cauta(nr%MOD,nr);
    for(i=l;i<n;i++){
        nr=(nr-p3*(buffer[i-l]-'a'))*3+buffer[i]-'a';
        con+=cauta(nr%MOD,nr);
    }
    fprintf(fout,"%d" ,con);
    fclose(fi);
    fclose(fout);
    return 0;
}