Cod sursa(job #1896389)

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

#define a 10
#define MOD 1000003
using namespace std;

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

string s1, s2;
int nr;

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

	long long  hash = 0;
	long long pow = 1;
	for (int i = 0; i < s1.size(); i++)
		hash = (hash * a % MOD + s1[i]) % MOD, pow = pow * a % MOD;

	long long rolling_hash = 0;
	for (int i = 0; i < s1.size(); i++)
		rolling_hash = (rolling_hash * a % MOD + s2[i]) % MOD;

	if (rolling_hash == hash)
		nr++;

	for (int i = s1.size(); i < s2.size(); i++)
	{
		rolling_hash = (rolling_hash * a % MOD - s2[i - s1.size()] * pow % MOD + s2[i]) % MOD;
		if (rolling_hash == hash)
			nr++;
	}

	fout << nr;
	return 0;
}