Cod sursa(job #2261177)

Utilizator aurelionutAurel Popa aurelionut Data 16 octombrie 2018 00:18:23
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>	
#include <unordered_map>
#include <cstring>

using namespace std;

const int MOD = 777013;
const int HASH = 101;
const int NMAX = 1e7 + 10;
const int MMAX = 5e4 + 10;
char s[NMAX], a[MMAX];
bool mp[MOD];
int n, m, val = 1;

inline int RepairMod(long long x)
{
	while (x > MOD)
		x -= MOD;
	while (x < 0)
		x += MOD;
	return x;
}

int main()
{
	ifstream fin("abc2.in");
	ofstream fout("abc2.out");
	fin >> (s + 1);
	n = strlen(s + 1);
	int hashCode;
	while (fin >> (a + 1))
	{
		if (m == 0)
		{
			m = strlen(a + 1);
			for (int j = 1;j <= m;++j)
				val = RepairMod(val * HASH);
		}
		hashCode = 0;
		for (int j = 1;j <= m;++j)
			hashCode = RepairMod(1LL * hashCode * HASH + (a[j] - 'a' + 1));
		mp[hashCode] = true;
	}
	hashCode = 0;
	int cnt = 0;
	for (int i = 1;i <= n;++i)
	{
		hashCode = RepairMod(1LL * hashCode * HASH + (s[i] - 'a' + 1));
		if (i > m)
			hashCode = RepairMod(1LL * hashCode - 1LL * (s[i - m] - 'a' + 1) * val);
		if (i >= m && mp[hashCode] == true)
			++cnt;
	}
	fout << cnt << "\n";
	fin.close();
	fout.close();
	return 0;
}