Cod sursa(job #2261189)

Utilizator aurelionutAurel Popa aurelionut Data 16 octombrie 2018 01:34:22
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 1e7 + 10;
const int MMAX = 5e4 + 10;
const int Base = 3;
const int MOD = 123457;
char Text[NMAX], Word[MMAX];
vector <int> Hash[MOD];

inline void insertHash(const long long &x)
{
	Hash[x % MOD].push_back(x);
}

bool findHash(const long long &x)
{
	int key = x % MOD;
	for (auto i : Hash[key])
		if (i == x)
			return true;
	return false;
}

int main()
{
	ifstream fin("abc2.in");
	ofstream fout("abc2.out");
	int WordSize, TextSize;
	fin >> (Text + 1);
	TextSize = strlen(Text + 1);
	unsigned int hashCode;
	while (fin >> (Word + 1))
	{
		WordSize = strlen(Word + 1);
		hashCode = 0;
		for (int i = 1;i <= WordSize;++i)
			hashCode = hashCode * Base + (Word[i] - 'a');
		insertHash(hashCode);
	}
	unsigned int p = 1;
	for (int i = 1;i < WordSize;++i)
		p *= Base;
	hashCode = 0;
	for (int i = 1;i <= WordSize;++i)
		hashCode = hashCode * Base + (Text[i] - 'a');
	int answer = findHash(hashCode);
	for (int i = WordSize + 1;i <= TextSize;++i)
	{
		hashCode -= (Text[i - WordSize] - 'a') * p;
		hashCode = hashCode * Base + (Text[i] - 'a');
		if (findHash(hashCode))
			++answer;
	}
	fout << answer << "\n";
	fin.close();
	fout.close();
	return 0;
}