Cod sursa(job #530999)

Utilizator icepowdahTudor Didilescu icepowdah Data 8 februarie 2011 19:26:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <string>
using namespace std;

#define MAXN 2000001
#define MAX_MATCHES 1000
#define PRIME_MULT 101
#define PRIME_MOD1 573527
#define PRIME_MOD2 574297

char A[MAXN], B[MAXN];
int lenA, lenB, matches, indices[MAX_MATCHES];

int main()
{
	int hashA1, hashA2, hashB1, hashB2, pow1, pow2;
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	scanf("%s %s", A, B);
	lenA = strlen(A); lenB = strlen(B);
	if (lenA > lenB) {
		printf("0\n");
		return 0;	
	}
	hashA1 = hashA2 = A[0], hashB1 = hashB2 = B[0]; pow1 = pow2 = 1;	
	for (int i = 1; i < lenA; i++)	{
		hashA1 = (hashA1 * PRIME_MULT + A[i]) % PRIME_MOD1;
		hashA2 = (hashA2 * PRIME_MULT + A[i]) % PRIME_MOD2;
		hashB1 = (hashB1 * PRIME_MULT + B[i]) % PRIME_MOD1;
		hashB2 = (hashB2 * PRIME_MULT + B[i]) % PRIME_MOD2;
		pow1 = (pow1*PRIME_MULT) % PRIME_MOD1;			
		pow2 = (pow2*PRIME_MULT) % PRIME_MOD2;			
	}
	if (hashA1 == hashB1 && hashA2 == hashB2) {
		indices[matches++] = 0;
	}
	for (int i = lenA; i < lenB; i++)
	{
		hashB1 = ((hashB1 - (B[i - lenA] * pow1) % PRIME_MOD1 + PRIME_MOD1) * PRIME_MULT + B[i]) % PRIME_MOD1;
		hashB2 = ((hashB2 - (B[i - lenA] * pow2) % PRIME_MOD2 + PRIME_MOD2) * PRIME_MULT + B[i]) % PRIME_MOD2;
		if (hashA1 == hashB1 && hashA2 == hashB2) {
			if (matches<MAX_MATCHES) {
				indices[matches] = i-lenA+1;
			}
			matches++;
		}
	}
	printf("%d\n", matches);
	int limit = (matches<=MAX_MATCHES)?matches:MAX_MATCHES;
	for (int i=0;i<limit;i++) {
		printf("%d ",indices[i]);
	}
	printf("\n");	
	return 0;
}