Cod sursa(job #683409)

Utilizator balakraz94abcd efgh balakraz94 Data 20 februarie 2012 16:38:07
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<cstdio>
#include<vector>
#include<cstring>
#define infile "abc2.in"
#define outfile "abc2.out"
#define t_max 10000005
#define n_max 50005
#define Base 3
#define dim_max 21
#define MOD 90907
#define ui unsigned int
#define FOR(g) \
	for(vector<ui>::iterator it=g.begin(); it!=g.end(); ++it)
using namespace std;


char T[t_max], S[dim_max];

int N, M, NrCuv;

vector < ui > HT[MOD];

ui Val[n_max];

ui Sol;


inline int tonum ( char x ){
	return x - 'a'; }


void make_hash()
{
	if(!strlen(S))
		return;
	
	if(!M)
		M = strlen(S);
	
	ui x = 0;
	for(int i=0; i < M; ++i)
		x = Base * x + tonum(S[i]);
		
	int where = x % MOD;
	
	FOR(HT[where])
		if(*it == x)
			return;
		
	Val[++NrCuv] = x;
	
	HT[where].push_back(x);
}


void citeste()
{
	freopen(infile, "r", stdin);
	
	gets(T);
	N = strlen(T);
	
	while(gets(S))
		make_hash();
	
	fclose(stdin);
}


void Rabin_Karp()
{	
	ui ValT = 0, P = 1;
	
	for(int i=0; i < M; ++i)
	{
		ValT = Base * ValT + tonum(T[i]);
		
		if(i)
			P = Base * P;
	}
	
	for(int i=0; i <= N - M; ++i)
	{
		for(int j=1; j <= NrCuv; ++j)
			if(Val[j] == ValT)
				Sol++;
		
        ValT = Base * (ValT - tonum(T[i]) * P) + tonum(T[i+M]);
	}
}



void afiseaza()
{
	freopen(outfile, "w", stdout);
	
	printf("%d\n", Sol);
	
	fclose(stdout);
}



int main()
{
	citeste();
	
	Rabin_Karp();
	
	afiseaza();
	
	return 0;
}