Cod sursa(job #237513)

Utilizator luk17Luca Bogdan luk17 Data 29 decembrie 2008 22:24:26
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define mod1 1000007
#define mod2 1000023
using namespace std;
char a[10000001],cuv[30];
long treila1[21],treila2[30],val1,val2;
int nrap;
long h1(int m, char *s)
{
	int i,prod=0;
	for(i=0;i<m;i++)
		prod=(prod+treila1[m-i-1]*(s[i]-'a'))%mod1;
	return prod;
}
long h2(int m, char *s)
{
	int i,prod=0;
	for(i=0;i<m;i++)
		prod=(prod+treila2[m-i-1]*(s[i]-'a'))%mod2;
	return prod;
}


int main()
{
	int i,n,m;
	vector <long> hash1,hash2;
	hash1.reserve(50001);
	hash2.reserve(50001);
	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);
	treila1[0]=treila2[0]=1;
	for(i=1;i<=20;i++)
	{
		treila1[i]=(treila1[i-1]*3)%mod1;
		treila2[i]=(treila2[i-1]*3)%mod2;
	}
	
	hash1.push_back(h1(m,cuv));	
	hash2.push_back(h2(m,cuv));	
	
	while(!feof(f))
	{
		fscanf(f,"%s",cuv);
		hash1.push_back(h1(m,cuv));	
		hash2.push_back(h2(m,cuv));	
	}
	
	sort(hash1.begin(),hash1.end());
	sort(hash1.begin(),hash1.end());
	
	val1=h1(m,a);
	val2=h2(m,a);
	if(find(hash1.begin(),hash1.end(),val1)!=hash1.end()&&find(hash2.begin(),hash2.end(),val2)!=hash2.end())
			nrap++;
	for(i=1;i<=n-m+1;i++)
	{	val1=((val1-treila1[m-1]*(a[i-1]-'a')+mod1)*3+(a[i+m-1]-'a'))%mod1;
		val2=((val2-treila2[m-1]*(a[i-1]-'a')+mod2)*3+(a[i+m-1]-'a'))%mod2;
		if(find(hash1.begin(),hash1.end(),val1)!=hash1.end()&&find(hash2.begin(),hash2.end(),val2)!=hash2.end())
			nrap++;
	}

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