Cod sursa(job #474844)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 5 august 2010 11:14:08
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

#define file_in "abc2.in"
#define file_out "abc2.out"

#define nmax 10000005 
#define sigma 26
#define mod 666013

int n,N;
char s[sigma];
char S[nmax];
vector<unsigned int> hash[mod+sigma];


void baga(int x)
{
	vector<unsigned int> :: iterator it;
	int k=x%mod;
	for (it=hash[k].begin();it!=hash[k].end();++it)
		 if (*it==x)
			 return ;//mai e
	hash[k].push_back(x);
}	

int cauta(int x)
{
	vector<unsigned int> :: iterator it;
	int k=x%mod;
	for (it=hash[k].begin();it!=hash[k].end();++it)
		 if (*it==x)
			 return 1;//l-am gasit
	return 0;	 
	
}	


void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	fgets(S,nmax,stdin);
	N=strlen(S)-1;
	fgets(s,sigma,stdin);
	n=strlen(s)-1;
	do
	{
		unsigned int nr=0;
		for (int i=0;i<n;++i)
			 nr=3*nr+s[i]-'a';
		baga(nr);	 
	}
	while(fgets(s,sigma,stdin));
}

void solve()
{
	int i;
	unsigned int pow3=1,nr=0,sol=0;
	
	for (i=0;i<n-1;++i)
	{
		nr=3*nr+S[i]-'a';
		pow3*=3;
	}
	for (i=n-1;i<N;++i)
	{
		nr=3*(nr%pow3)+S[i]-'a';
		sol+=(cauta(nr));
	}
	
	printf("%d\n", sol);
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}