Cod sursa(job #683097)

Utilizator balakraz94abcd efgh balakraz94 Data 19 februarie 2012 22:57:27
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 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 dim_max 21
#define Base 3
#define MOD1 100007
#define MOD2 100021
using namespace std;


char T[t_max];
int N;

char P[n_max][dim_max];
int  NP;

bitset < MOD2 > uz1, uz2;

int Sol;

void citeste()
{
	freopen(infile, "r", stdin);
	
	gets(T);
	N = strlen(T);
	
	while(gets(P[++NP]));
	
	fclose(stdin);
}


void Rabin_Karp(char *P)
{
	int M = strlen(P);

	int HP1, HP2, HT1, HT2;
	int P1, P2;
	
	HP1 = HP2 = HT1 = HT2 = 0;
	P1 = P2 = 1;
	
	for(int i=0; i<M; ++i)
	{
		HP1 = (Base * HP1 + P[i]) % MOD1;
		HP2 = (Base * HP2 + P[i]) % MOD2;
		
		HT1 = (Base * HT1 + T[i]) % MOD1;
		HT2 = (Base * HT2 + T[i]) % MOD2;
		
		if(i){
			P1 = (Base * P1) % MOD1;
			P2 = (Base * P2) % MOD2;
		}
	}
	
	if(uz1[HP1] && uz2[HP2])
		return;
	
	uz1[HP1] = uz2[HP2] = 1;
	
	for(int i=0; i<= N - M; ++i)
	{
		if(HT1 == HP1 && HT2 == HP2)
			Sol++;
		
		HT1 = (Base * (HT1 - (T[i] * P1) % MOD1 + MOD1) + T[i+M]) % MOD1;
		HT2 = (Base * (HT2 - (T[i] * P2) % MOD2 + MOD2) + T[i+M]) % MOD2;
	}
}



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



int main()
{
	citeste();
	
	for(int i=1; i < NP; ++i)
		Rabin_Karp(P[i]);
	
	afiseaza();
	
	return 0;
}