Cod sursa(job #812712)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 14 noiembrie 2012 11:50:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define B1 71
#define mod1 100021
#define mod2 100007

const int MAXN = 2000005;
using namespace std;

char A[MAXN], B[MAXN];
int n, m, hash1, hash2, H1, H2;
int v[1005];

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	scanf("%s\n", A + 1); n = strlen(A + 1);
	scanf("%s\n", B + 1); m = strlen(B + 1);
	
	int P1 = 1, P2 = 1;
	
	for(int i = 1; i <= n; ++i) {
		hash1 = (hash1 * B1 + A[i]) % mod1;
		hash2 = (hash2 * B1 + A[i]) % mod2;
		
		P1 = (P1 * B1) % mod1;
		P2 = (P2 * B1) % mod2;
	
	}
//	printf("%d %d\n", P1, P2);
	for(int i = 1; i <= n; ++i) {
		H1 = (H1 * B1 + B[i]) % mod1;
		H2 = (H2 * B1 + B[i]) % mod2;
	}
	
	if(H1 == hash1 && H2 == hash2)
		v[++v[0]] = 1;
	
	for(int i = n + 1; i <= m; ++i) {
		H1 = (H1 * B1 + B[i]) % mod1;
		H2 = (H2 * B1 + B[i]) % mod2;
		
		H1 = (H1 - (B[i - n] * P1) % mod1 + mod1) % mod1;
		H2 = (H2 - (B[i - n] * P2) % mod2 + mod2) % mod2;
		
		//printf("%d %d %d %d\n", hash1, H1, hash2, H2);
		
		if(H1 == hash1 && H2 == hash2) {
			++v[0];
			if(v[0] >= 1000) continue;
			v[v[0]] = i - n + 1;
		}
	}
	printf("%d\n", v[0]);
	for(int i = 1; i <= min(999,v[0]); ++i)
		printf("%d ", v[i] - 1);
	
	return 0;
}