Cod sursa(job #105800)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 17 noiembrie 2007 23:30:47
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.27 kb
#include <cstdio>
#include <cstring>
#define NR_PRIM 1000231
struct lista {
    long long inf;
    lista *urm;
} *hash[NR_PRIM];
char t[10000005];
int defined=0;
char p[24];


void init(void){
    long long i;
    freopen("abc2.in","rt",stdin);
    freopen("abc2.out","wt",stdout);
    scanf("%s",t+1);
    for (i=0;i<=NR_PRIM-1;hash[i]=NULL,i++);
}


long long codif(const char* p){
    long long putere=1,i,sum=0;
    for (i=1;i<defined;putere*=4,i++);
    for (i=1;i<=defined;sum+=(p[i]-'a'+1)*putere,putere/=4,i++);
    return sum;
}


void build_hash(void){
    long long i,nr;
    lista *q;
    while (!feof(stdin)){
        scanf("%s",p+1);
    if (defined==0){
        defined=strlen(p+1);
    }
    q=new lista;
    nr=codif(p);
    q->inf=nr;
    q->urm=hash[nr%NR_PRIM];
    hash[nr%NR_PRIM]=q;
    }
}


void verify(void){
    long long nr,i,putere=1,nrpos=0;
    lista *q;
    for (i=1;i<defined;putere*=4,i++);
    defined--;
    nr=codif(t);
    defined++;
    for (i=defined;i<=strlen(t+1);i++){
        nr=((nr%putere)*4)+(t[i]-'a'+1);
        for (q=hash[nr%NR_PRIM];q &&  (q->inf != nr);q=q->urm);
        if (q){
            nrpos++;
        }
    }
    printf("%ld\n",nrpos);
    fclose(stdout);
}


int main(void){
    init();
    build_hash();
    verify();
    return 0;
}