Cod sursa(job #245694)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 18 ianuarie 2009 17:07:01
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#define N 50007

int v[30],enc[N];
char s[200*N],dict[30];
int n,m,k,val,nr;

int caut_bin(int *q,int l,int c){
	int op,r=1;
	for(op=1;op<l;op<<=1);
	for(;op;op>>=1)
		if((r+op<=l)&&(q[r+op]<=c))
			r+=op;
		if(q[r]==c)
			return 1;
		return 0;
}

void calc(){
	int i;
	for(i=1;i<=n-m+1;++i){
		val-=v[m-1]*(s[i-1]-'s');
		val=val*3+s[i+m-1]-'s';
		if(caut_bin(enc,k,val))
			nr++;
	}
	printf("%d\n",nr);
}

int add(int m,char *s){
	int i,p=0;
	for(i=0;i<m;++i)
		p+=v[m-i-1]*(s[i]-'s');
	return p;
}

void citire(){
	int i;
	scanf("%s",s);
	scanf("%s",dict);
	n=strlen(s);
	m=strlen(dict);
	v[0]=1;
	for(i=1;i<=m;++i)
		v[i]=v[i-1]*3;
	enc[1]=add(m,dict);
	k=1;
	while(scanf("%s",dict)!=EOF){
		enc[++k]=add(m,dict);
	}
}

int main(){
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	citire();
	std::sort(enc+1,enc+1+k);
	val=add(m,s);
	if(caut_bin(enc,k,val))
		nr=1;
	calc();
	fclose(stdin);
	fclose(stdout);
	return 0;
}