Cod sursa(job #470735)

Utilizator bog29Antohi Bogdan bog29 Data 15 iulie 2010 13:34:54
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
#include<vector>
#include<math.h>
#define dmax 10000004
#define dmax2 50004
#define md 666013
#define bz 3

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

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

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


void geth()
{	unsigned int nr=0,n,i,k;
	
	n=strlen(cuv);
	
	for(i=0;i<n;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()
{	unsigned int i,lng,h=0,k;
	
	for(i=0;i<m;i++)
		h=bz*h + l[i]-'a' ;
	
	k=h%md;
	
	if(!g[k].empty() )
		for(it=g[k].begin();it<g[k].end();it++)	
			if(*it==h)
				sol++;
	
	lng=strlen(l);
	
	for(i=0;i < lng-m ;i++)
	{	
		h=bz*(h-(l[i]-'a')*(int)pow(bz,m-1))+l[i+m]-'a';
		
		k=h%md;
		
		if(!g[k].empty() )
			for(it=g[k].begin();it<g[k].end();it++)	
				if(*it==h)
					sol++;
	}	
}	

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