Cod sursa(job #2261200)

Utilizator aurelionutAurel Popa aurelionut Data 16 octombrie 2018 01:44:48
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>	
#include <cstring>

using namespace std;

const int MOD1 = 777013;
const int MOD2 = 123457;
const int HASH1 = 101;
const int HASH2 = 23;
const int NMAX = 1e7 + 10;
const int MMAX = 31;
char s[NMAX], a[MMAX];
bool mp1[MOD1], mp2[MOD2];
int n, m, val1 = 1, val2 = 1;

inline int RepairMod(long long x, const int &MOD)
{
	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 hashCode1, hashCode2;
	while (fin >> (a + 1))
	{
		if (m == 0)
		{
			m = strlen(a + 1);
			for (int j = 1;j <= m;++j)
			{
				val1 = RepairMod(val1 * HASH1, MOD1);
				val2 = RepairMod(val2 * HASH2, MOD2);
			}
		}
		hashCode1 = hashCode2 = 0;
		for (int j = 1;j <= m;++j)
		{
			hashCode1 = RepairMod(1LL * hashCode1 * HASH1 + (a[j] - 'a' + 1), MOD1);
			hashCode2 = RepairMod(1LL * hashCode2 * HASH2 + (a[j] - 'a' + 1), MOD2);
		}
		mp1[hashCode1] = true;
		mp2[hashCode2] = true;
	}
	hashCode1 = hashCode2 = 0;
	int cnt = 0;
	for (int i = 1;i <= n;++i)
	{
		hashCode1 = RepairMod(1LL * hashCode1 * HASH1 + (s[i] - 'a' + 1), MOD1);
		hashCode2 = RepairMod(1LL * hashCode2 * HASH2 + (s[i] - 'a' + 1), MOD2);
		if (i > m)
		{
			hashCode1 = RepairMod(1LL * hashCode1 - 1LL * (s[i - m] - 'a' + 1) * val1, MOD1);
			hashCode2 = RepairMod(1LL * hashCode2 - 1LL * (s[i - m] - 'a' + 1) * val2, MOD2);
		}
		if (i >= m && mp1[hashCode1] == true && mp2[hashCode2] == true)
			++cnt;
	}
	fout << cnt << "\n";
	fin.close();
	fout.close();
	return 0;
}