Cod sursa(job #1896404)

Utilizator horiainfoTurcuman Horia horiainfo Data 28 februarie 2017 17:53:40
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <string>

#define a 10
#define MOD1 1000003
#define MOD2 1000037
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string s1, s2;
int nr;

int main()
{
	fin >> s1;
	fin >> s2;

	long long  hashA1 = 0, hashA2 = 0;
	long long pow1 = 1, pow2 = 1;
	for (int i = 0; i < s1.size(); i++)
	{
		hashA1 = (hashA1 * a % MOD1 + s1[i]) % MOD1, pow1 = pow1 * a % MOD2;
		hashA2 = (hashA2 * a % MOD2 + s1[i]) % MOD2, pow2 = pow2 * a % MOD2;
	}

	long long hashB1 = 0, hashB2 = 0;
	for (int i = 0; i < s1.size(); i++)
	{
		hashB1 = (hashB1 * a % MOD1 + s2[i]) % MOD1;
		hashB2 = (hashB2 * a % MOD2 + s2[i]) % MOD2;
	}

	if (hashA1 == hashB1 && hashA2 == hashB2)
		nr++;

	for (int i = s1.size(); i < s2.size(); i++)
	{
		hashB1 = (hashB1 * a % MOD1 - s2[i - s1.size()] * pow1 % MOD1 + s2[i]) % MOD1;
		hashB2 = (hashB2 * a % MOD2 - s2[i - s1.size()] * pow2 % MOD2 + s2[i]) % MOD2;
		if (hashA1 == hashB1 && hashA2 == hashB2)
			nr++;
	}

	fout << nr;
	return 0;
}