Cod sursa(job #824402)

Utilizator horeste12Stoianovici Horatiu Andrei horeste12 Data 26 noiembrie 2012 16:00:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<cstdio>
#include<malloc.h>
#include<cstring>
#include<vector>
#define baza 123
#define modulo1 1000003
#define modulo2 1000033

using namespace std;
int main()
{
	int baseHash1 = 0, currentHash1 = 0, baseHash2 = 0, currentHash2 = 0;
	int n, m;
	int P1, P2;
	int ok = 1;
	vector<int> matches;
	char *a = new char[2000010];
	char *b = new char[2000010];

	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	scanf("%s %s", a, b);
	n = strlen(b);
	m = strlen(a);

	for(int i = 0; i < m; i++)
	{
		if(i > 0)
		{
			P1 = (P1 * baza) % modulo1;
			P2 = (P2 * baza) % modulo2;
		}
		else
		{
			P1 = 1;
			P2 = 1;
		}
		baseHash1 = (baseHash1 * baza + a[i]) % modulo1;
		baseHash2 = (baseHash2 * baza + a[i]) % modulo2;

		currentHash1 = (currentHash1 * baza + b[i]) % modulo1;
		currentHash2 = (currentHash2 * baza + b[i]) % modulo2;
	}

	if(currentHash1 == baseHash1 && currentHash2 == baseHash2)
		matches.push_back(0);

	for(int i = m; i < n && ok; i++)
	{
		currentHash1 = ((currentHash1 - P1 * b[i - m] % modulo1 + modulo1) * baza + b[i]) % modulo1;
		currentHash2 = ((currentHash2 - P2 * b[i - m] % modulo2 + modulo2) * baza + b[i]) % modulo2;

		if(currentHash1 == baseHash1 && currentHash2 == baseHash2)
			if(matches.size() < 1000)
				matches.push_back(i - m + 1);
			else
				ok = 0;
	}

	printf("%d\n", matches.size());
	for(vector<int>::iterator i = matches.begin(); i < matches.end(); i++)
		printf("%d ", *i);
	puts("");

	return 0;
}