Cod sursa(job #630588)

Utilizator mihai0110Bivol Mihai mihai0110 Data 5 noiembrie 2011 21:42:05
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <vector>
#include <cstring>

#define MOD 90907

using namespace std;

char s[10000010];
char word[21];

vector<unsigned int> table[MOD];

int search_table(unsigned int hash) {
	unsigned int n = table[hash % MOD].size();
	for(unsigned int i = 0; i < n; i++)
		if(table[hash % MOD][i] == hash)
			return 1;
	return 0;
}

void add_to_table(unsigned int hash) {
	if (!search_table(hash))
		table[hash % MOD].push_back(hash);
}
		
int main(void) {
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);

	scanf("%s", s);
	unsigned int i = 0;
	unsigned int hash = 0;
	unsigned int len;
	while(!feof(stdin)) {
		scanf("%s", word);
		len = strlen(word);
		hash = 0;
		for(i = 0; i < len; i++)
			hash = (hash * 3 + word[i] - 'a');
		add_to_table(hash);
	}
	unsigned int sol = 0;
	unsigned int offset = 1;
	hash = 0;
	for(i = 0; i < len; i++) {
		hash = hash * 3 + s[i] - 'a';
		offset *= 3;
	}
	offset /= 3;

	sol += search_table(hash);
	unsigned int slen = strlen(s);

	for(i = len; i < slen; i++) {
		hash = (hash - offset * (s[i - len] - 'a')) * 3 + s[i] - 'a';
		sol += search_table(hash);
	}
	printf("%ld\n", sol);
	return 0;
}