Cod sursa(job #470747)

Utilizator bog29Antohi Bogdan bog29 Data 15 iulie 2010 13:53:51
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<fstream>
#include<vector>
#include<math.h>
#define dmax 10000004
#define md 666013
#define bz 3

using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");

char l[dmax],cuv[23];
int n,m;
int sol;

vector<unsigned int>g[md+100];
vector<unsigned int>::iterator it;


void geth()
{	unsigned int nr=0;
	int i,k;
	
	for(i=0;i<m;i++)
		nr=nr*3+(cuv[i]-'a');
	
	k=nr%md;
	
	for(it=g[k].begin();it<g[k].end();it++)
		if(*it==nr)
			return;
	
	g[k].push_back(nr);
}


	
void search()
{	int i,k;
	unsigned int h=0,p=1;
	
	for(i=0;i<m-1;i++)
	{	h=h*bz+(l[i]-'a');
		p*=bz;
	}

	for(i=m-1;i<n;i++)
	{	h=(h%p)*bz+(l[i]-'a');
		k=h%md;
		for(it=g[k].begin();it<g[k].end();it++)	
			if(*it==h)
				sol++;
				
	}		
	
}	

int main()
{	int i;
	in.getline(l,dmax,'\n');
	n=strlen(l);
	while(!in.eof() )
	{	in.getline(cuv,23,'\n');
		if(!m)m=strlen(cuv);
		geth();
	}
	in.close();
	search();
	out<<sol;
	out.close();
	return 0;
}