Cod sursa(job #105928)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 18 noiembrie 2007 09:09:21
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 0.91 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 8500000
unsigned int v[50001],n=0;
int compar(const void *a,const void *b){
	unsigned int *aa=(unsigned int*)a,*bb=(unsigned int*)b;
	if(*aa<*bb)
		return -1;
	if(*aa>*bb)
		return 1;
	return 0;
}
int caut(unsigned int x){
	unsigned int i,p;
	for(p=1;p<n;p<<=1);
	for(i=0;p;p>>=1)
		if(i+p<n&&v[i+p]<=x)
			i+=p;
	return i<N&&v[i]==x?1:0;
}
int main(){
	unsigned int i,m,x=0,r=0,y=1;
	char s[N],c[25],*p;
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	scanf("%s\n",s);
	while(scanf("%s\n",c)!=EOF){
		v[n]=0;
		for(p=c;*p;++p)
			v[n]=v[n]*3+(*p-'a');
		n++;
	}
	qsort(v,n,sizeof(v[0]),compar);
	m=strlen(c);
	for(i=0;i<m;++i){
		x=x*3+(s[i]-'a');
		y*=3;
	}
	y/=3;
	r+=caut(x);
	for(p=s+m;*p;++p){
		x=x%y*3+(*p-'a');
		r+=caut(x);
	}
	printf("%d\n",r);
	fclose(stdin);
	fclose(stdout);
	return 0;
}