Cod sursa(job #168460)

Utilizator MariusMarius Stroe Marius Data 31 martie 2008 14:12:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <set>
#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];

set <unsigned int> hash[524288];

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

	int ret = 0;

	fin.getline(T, MAXN);
	n = (int)strlen(T);
	fin.getline(word, 21);
	m = (int)strlen(word);
	while (*word)
	{
		h = 0;
		for (char *p = word; *p; ++ p)
			h = h * 3 + (*p - 'a');
		hash[h & 524287u].insert(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');
	FOR (i, 0, n-m+1)
	{
		h2 = h & 524287u;
		if (hash[h2].find(h) != hash[h2].end())
			ret ++;
		if (i + m < n)
			h = (h - bpm * (T[i] - 'a')) * 3 + (T[i + m] - 'a');
	}

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

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