Cod sursa(job #683287)

Utilizator balakraz94abcd efgh balakraz94 Data 20 februarie 2012 13:32:05
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<cstdio>
#include<cstring>
#include<bitset>
#include<vector>
#define infile "abc2.in"
#define outfile "abc2.out"
#define t_max 10000005
#define n_max 50005
#define Base 3
#define dim_max 21
#define MOD1 9931
#define MOD2 9923
using namespace std;


char T[t_max], S[dim_max];

unsigned int N, M;

unsigned int HP1[n_max], HP2[n_max];

unsigned int NH;

bitset < MOD1 > uz1, uz2;

unsigned int Sol;


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


void make_hash()
{
	if(!strlen(S))
		return;
	
	if(!M)
		M = strlen(S);
	
	HP1[++NH] = HP2[NH] = 0;
	
	for(unsigned int i=0; i < M; ++i)
	{
		HP1[NH] = (Base * HP1[NH] + tonum(S[i])) % MOD1;
		HP2[NH] = (Base * HP2[NH] + tonum(S[i])) % MOD2;
	}
	
	if(uz1[HP1[NH]] && uz2[HP2[NH]])
		{ NH--; return;}
	
	uz1[HP1[NH]] = uz2[HP2[NH]] = 1;
}


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


void Rabin_Karp()
{	
	unsigned int HT1, HT2, P1, P2;
	
	HT1 = HT2 = 0;
	P1 = P2 = 1;
	
	for(unsigned int i=0; i < M; ++i)
	{
		HT1 = (Base * HT1 + tonum(T[i])) % MOD1;
		HT2 = (Base * HT2 + tonum(T[i])) % MOD2;
		
		if(i)
		{
			P1 = (Base * P1) % MOD1;
			P2 = (Base * P2) % MOD2;
		}
	}
	
	for(unsigned int i=0; i <= N - M; ++i)
	{
		for(unsigned int j=1; j <= NH; ++j)
			if(HP1[j] == HT1 && HP2[j] == HT2)
				Sol++;
			
	    HT1 = (Base * (HT1 - (tonum(T[i]) * P1) % MOD1 + MOD1) + tonum(T[i+M])) % MOD1;
		HT2 = (Base * (HT2 - (tonum(T[i]) * P2) % MOD2 + MOD2) + tonum(T[i+M])) % MOD2;
	}
}



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



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