Cod sursa(job #808638)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 7 noiembrie 2012 01:35:34
Problema Potrivirea sirurilor Scor 22
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

int p, t;
int size;
int ans[2000002];
char P[2000002], T[2000002];

const int MOD1 = 1000003;
const int MOD2 = 1000007;

const int RADIX = 26 + 26 + 10;

int p1, p2, t1, t2;

int pow1 = 1, pow2 = 1;

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

	scanf("%s %s", P, T);

	p = strlen(P);
	t = strlen(T);

	if (p > t) {
		printf("0");
		return 0;
	}

	for (int i = 0; i < p; i++) {
		p1 = (p1 * RADIX + P[i]) % MOD1;
		p2 = (p2 * RADIX + P[i]) % MOD2;

		t1 = (t1 * RADIX + T[i]) % MOD1;
		t2 = (t2 * RADIX + T[i]) % MOD2;
		if (i != 0) {
			pow1 = (pow1 * RADIX) % MOD1;
			pow2 = (pow2 * RADIX) % MOD2;
		}
	}

	if (p1 == t1 && p2 == t2) {
		ans[size++] = 0;
	}

	for (int i = p; i < t; i++) {
		t1 = ((((t1 - T[i - p] * pow1) * RADIX + T[i]) % MOD1) + MOD1) % MOD1;
		t2 = ((((t2 - T[i - p] * pow2) * RADIX + T[i]) % MOD2) + MOD2) % MOD2;
		if (p1 == t1 && p2 == t2) {
			ans[size++] = i - p + 1;
		}
	}

	printf("%d\n", size);
	for (int i = 0; i < min(size, 1000); i++) {
		printf("%d ", ans[i]);
	}
	return 0;
}