Cod sursa(job #557034)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 16 martie 2011 13:50:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <string>
#include <cstring>
#define B1 29
#define B2 73
#define m1 666013
#define m2 100007
#define maxn 2000010
using namespace std;


int N, M, hash1, hash2, H1, H2, nr;
bool m[maxn];
char A[maxn], B[maxn];
int main ()
{

	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
	
	int i, j, p1, p2;
	scanf ("%s\n%s\n", A + 1, B + 1);
	
	N = strlen (A + 1);
	M = strlen (B + 1);
	
	if (N > M) {
		printf ("0\n");
		return 0;
	}
	
	p1 = p2 = 1;
	for (i = 1; i <= N; i++) {
		hash1 = (hash1 * B1 + A[i]) % m1;
		hash2 = (hash2 * B2 + A[i]) % m2;
		if (i != 1) {
			p1 = (p1 * B1) % m1;
			p2 = (p2 * B2) % m2;
		}
	}

	for (i = 1; i <= N; i++) {
		H1 = (H1 * B1 + B[i]) % m1;
		H2 = (H2 * B2 + B[i]) % m2;
	}
	if (hash1 == H1 && hash2 == H2) {
		++nr;
		m[1] = 1;
	}
	
	for (i = N + 1; i <= M; i++) {
	       H1 = ((H1 - (B[i - N] * p1) % m1 + m1) * B1 + B[i]) % m1;
	       H2 = ((H2 - (B[i - N] * p2) % m2 + m2) * B2 + B[i]) % m2;
	       if (H1 == hash1 && H2 == hash2) {
		       ++nr;
		       m[i - N + 1] = 1;
	       }
	}
	printf ("%d\n", nr);
	for (j = 0, i = 1; i <= M && j <= 1000; i++) 
		if (m[i]) {
			printf ("%d ", i - 1);
			++j;
		}
	return 0;
}