Cod sursa(job #237652)

Utilizator luk17Luca Bogdan luk17 Data 30 decembrie 2008 12:44:59
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[10000001],cuv[30];
long treila[30],val1,val2,hash1[50001],hash2[50001];
int nrap;
long h1(int m, char *s)
{
	int i;
	long prod=0;
	for(i=0;i<m;i++)
		prod=(prod+treila[m-i-1]*(s[i]-'a'));
	return prod;
}

 int caut_bin(long *vct,int el,long val)  
 {  
     int step = 1, rez = 1;  
     for (step = 1; step < el; step <<= 1);  
     for (; step; step >>= 1)  
         if (rez + step <= el && vct[rez + step] <= val)  
             rez += step;  
     if (vct[rez] == val)  
         return 1;  
     return 0;  
 }  
int main()
{
	int i,n,m,k;
	
	FILE *f=fopen("abc2.in","r");
	freopen("abc2.out","w",stdout);
	fscanf(f,"%s\n",a);
	fscanf(f,"%s\n",cuv);
	
	n=strlen(a);
	m=strlen(cuv);
	treila[0]=1;
	for(i=1;i<=m;i++)
			treila[i]=treila[i-1]*3;
	
	hash1[1]=h1(m,cuv);	
	
	k=1;
	while(!feof(f))
	{
		fscanf(f,"%s",cuv);
		hash1[++k]=h1(m,cuv);	
	}
	
	std::sort(hash1+1,hash1+1+k);
	val1=h1(m,a);
	
	if(caut_bin(hash1,k,val1))
			nrap++;
	for(i=1;i<=n-m+1;i++)
	{
		val1=(val1-treila[m-1]*(a[i-1]-'a'))*3+a[i+m-1]-'a';
		if(caut_bin(hash1,k,val1))
			nrap++;
	}

		printf("%d",nrap);
	fclose(f);
return 0;
}