Cod sursa(job #1498694)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 8 octombrie 2015 22:39:31
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#define uint unsigned int
#define MOD 666013
#define BAZA 3
#define MAXM 50000
#define MAXN 10000000
#define BUF_SIZE 4096
char s[MAXN], buf[BUF_SIZE];
int pos=BUF_SIZE, k, lista[MOD], next[MAXM+1];
uint val[MAXM+1];
FILE *fin;
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline void adauga(uint x){
    k++;
    val[k]=x;
    next[k]=lista[x%MOD];
    lista[x%MOD]=k;
}
inline int cauta(uint x){
    int p=lista[x%MOD];
    while(p){
        if(val[p]==x){
            return 1;
        }
        p=next[p];
    }
    return 0;
}
int main(){
    int ans, n, c, i;
    uint t, inv, aux, r;
    char ch;
    FILE *fout;
    fin=fopen("abc2.in", "r");
    fout=fopen("abc2.out", "w");
    ch=fgetc(fin);
    n=0;
    while(ch!='\n'){
        s[n++]=ch;
        ch=fgetc(fin);
    }
    ch=fgetc(fin);
    while(ch!=EOF){
        t=0;
        c=0;
        while(ch!='\n'){
            t=BAZA*t+ch-'a';
            c++;
            ch=fgetc(fin);
        }
        adauga(t);
        ch=fgetc(fin);
    }
    r=0;
    aux=1;
    inv=1;
    for(i=0; i<c; i++){
        aux=inv;
        inv=inv*BAZA;
        r=BAZA*r+s[i]-'a';
    }
    ans=cauta(r);
    inv=aux;
    for(i=c; i<n; i++){
        r=(r-inv*(s[i-c]-'a'))*BAZA+s[i]-'a';
        ans+=cauta(r);
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}