Cod sursa(job #532006)

Utilizator swift90Ionut Bogdanescu swift90 Data 10 februarie 2011 18:09:25
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int nrc,nc;
unsigned int cuv[50100],put,sc;
char s[10000100],c[100];
void caut(){
	int i,p;
	for(i=16,p=0;i>=0;--i){
		if(p+(1<<i)<=nc){
			if(cuv[p+(1<<i)]<=sc){
				p+=1<<i;
				if(cuv[p]==sc){
					++nrc;
					return;
				}
			}
		}
	}
}
int main(){
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	int i,j,lc;
	fgets(s,1<<25,stdin);
	fgets(c,100,stdin);
	for(put=1,i=0;'a'<=c[i] && c[i]<='z';++i){
		cuv[1]=cuv[1]*3+c[i]-'a';
		sc=sc*3+s[i]-'a';
	}
	lc=i;
	for(i=1;i<lc;++i)
		put*=3;
	j=1;
	while(fgets(c,100,stdin)){
		++j;
		for(i=0;i<lc;++i)
			cuv[j]=cuv[j]*3+c[i]-'a';
	}
	sort(cuv+1,cuv+j+1);
	nc=j;
	caut();
	for(j=0,i=lc;'a'<=s[i] && s[i]<='z';++i,++j){
		sc-=(s[j]-'a')*put;
		sc=sc*3+s[i]-'a';
		caut();
	}
	
	printf("%d\n",nrc);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}