Cod sursa(job #482643)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 4 septembrie 2010 12:26:47
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <algorithm>
#define Nmax 10000001
#define Nrcuv 50002
#define Lgcuv 22
#define P 3

using namespace std;

char s[Nmax];
char cuv[Lgcuv];
int v[Nrcuv];
int nr_cuv,lg_cuv;

inline int find(int x){
	int l=1,r=nr_cuv,m;
	while( l<=r ){
		m=l+(r-l)/2;
		if(v[m] == x ) return 1;
		if( v[m] < x) l=m+1;
		else r=m-1;
	}
	return 0;
}

int main(){
	int i,p,val,rez=0;
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	scanf("%s",s+1);
	while( !feof(stdin) ){
		scanf("%s",cuv+1);
		++nr_cuv;
		for(i=1; cuv[i]; ++i) 
			v[nr_cuv]=v[nr_cuv]*P+cuv[i]-'a';
	}
	lg_cuv=i-1;
	
	sort(v+1,v+nr_cuv+1);
	
	p=1; val=0;
	for(i=1;i<lg_cuv;++i) p=p*P;
	for(i=1;i<=lg_cuv;++i)
		val=val*P+s[i]-'a';
	if( find(val) ) rez=1; else rez=0;
	
	for(i=lg_cuv+1; s[i]; ++i){
		val -= (s[i-lg_cuv]-'a')*p;
		val=val*P+s[i]-'a';
		
		if( find(val) ) ++rez;
	}
	
	printf("%d\n",rez);
	fclose(stdin); fclose(stdout);
	return 0;
}