Pagini recente » Cod sursa (job #2800898) | Cod sursa (job #1423979) | Cod sursa (job #589618) | Cod sursa (job #596856) | Cod sursa (job #105795)
Cod sursa(job #105795)
#include <cstdio>
#include <cstring>
#define NR_PRIM 1000001
struct lista {
long inf;
lista *urm;
} *hash[NR_PRIM];
char t[10000005];
int defined=0;
char p[24];
void init(void){
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 codif(const char* p){
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 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 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;
}