Cod sursa(job #168467)

Utilizator MariusMarius Stroe Marius Data 31 martie 2008 14:25:06
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <algorithm>
using namespace std;

const char iname[] = "abc2.in";
const char oname[] = "abc2.out";

#define FOR(i, a, b)  for (int i = (a); i < (b); ++ i)
#define MAXN  10000001

char T[MAXN];

struct hash_node {
	unsigned int hash_value;
	hash_node *next;
} *hash_table[666777];

bool query(int index, unsigned int hash_value) {
	for (hash_node *p = hash_table[index]; p; p = p -> next)
		if (p -> hash_value == hash_value)
			return true;
	return false;
}

void insert(int index, unsigned int hash_value) {
	hash_node *p = new hash_node;
	p -> hash_value = hash_value, p -> next = hash_table[index], hash_table[index] = p;
}

int main(void)
{
	ifstream fin(iname);
	int n;
	int m = 0;
	char word[21], *p;
	unsigned int h;

	int ret = 0;

	fin.getline(T, MAXN);
	n = (int)strlen(T);
	fin.getline(word, 21);
	m = (int)strlen(word);
	while (*word)
	{
		h = 0;
		for (p = word; *p; ++ p)
			h = h * 3 + (*p - 'a');
		if (query(h % 666777, h) == false)
			insert(h % 666777, h);

		fin.getline(word, 21);
	}

	unsigned int bpm = 1;
	FOR (i, 0, m - 1)
		bpm *= 3;

	h = 0;
	FOR (i, 0, m)
		h = h * 3 + (T[i] - 'a');
	p = T;
	FOR (i, 0, n-m+1)
	{
		if (query(h % 666777, h))
			ret ++;
		if (i + m < n)
			h = (h - bpm * (*p - 'a')) * 3 + (p[m] - 'a');
		p ++;
	}

	ofstream fout(oname);
	
	fout << ret <<'\n';

	fin.close(), fout.close();
	return 0;
}