Cod sursa(job #482647)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 4 septembrie 2010 12:36:15
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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 i,step=0;
	for(step=1; step<=nr_cuv; step<<=1);
	step >>=1;
	for(i=1; step; step>>=1)
		if( i+step<=nr_cuv && v[i+step]<=x )
			i+=step;
	return v[i] == x;
}

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;
}