Cod sursa(job #1896468)

Utilizator horiainfoTurcuman Horia horiainfo Data 28 februarie 2017 18:29:36
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>

#define LG 2000002
#define a 73
#define MOD1 100003
#define MOD2 100027
using namespace std;

ofstream fout("strmatch.out");

char s1[LG], s2[LG];
vector<int> v;

int main()
{
	freopen("strmatch.in", "r", stdin);
	scanf("%s %s", &s1, &s2);

	int l1 = strlen(s1), l2 = strlen(s2);

	if (l1 > l2)
	{
		fout << 0;
		return 0;
	}

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

		if (i > 0)
		{
			pow1 = pow1 * a % MOD1;
			pow2 = pow2 * a % MOD2;
		}
	}

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

	if (hashA1 == hashB1 && hashA2 == hashB2)
		v.push_back(0);

	for (int i = l1; i < l2; i++)
	{
		hashB1 = ((hashB1 - s2[i - l1] * pow1 % MOD1 + MOD1) * a + s2[i]) % MOD1;
		hashB2 = ((hashB2 - s2[i - l1] * pow2 % MOD2 + MOD2) * a + s2[i]) % MOD2;
		if (hashA1 == hashB1 && hashA2 == hashB2)
			v.push_back(i - l1 + 1);
	}

	fout << v.size() << '\n';
	for (int i = 0; i < v.size(); i++)
		fout << v[i] << ' ';
	return 0;
}