Cod sursa(job #530124)

Utilizator icepowdahTudor Didilescu icepowdah Data 6 februarie 2011 21:55:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <string>
using namespace std;

#define MAXN 2000001
#define MAX_MATCHES 1000
#define PRIME_MULT 73
#define PRIME_MOD 100007

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

void countIfMatch(int startB) {
	for (int i=0;i<lenA;i++) {
		if (A[i]!=B[startB+i]) {
			return;
		}
	}
	if (matches<MAX_MATCHES) {
		indices[matches++] = startB;
	}
}

int main()
{
	int hashA, hashB, pow;
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);
	scanf("%s %s", A, B);
	lenA = strlen(A); lenB = strlen(B);
	if (lenA > lenB) {
		printf("0\n");
		return 0;	
	}
	hashA = hashB = 0; pow = 1;	
	for (int i = 0; i < lenA; i++)	{
		hashA = (hashA * PRIME_MULT + A[i]) % PRIME_MOD;
		hashB = (hashB * PRIME_MULT + B[i]) % PRIME_MOD;
		if ( i!= 0)
			pow = (pow*PRIME_MULT) % PRIME_MOD;
	}
	if (hashA == hashB) {
		countIfMatch(0);
	}
	for (int i = lenA; i < lenB; i++)
	{
		hashB = ((hashB - (B[i - lenA] * pow) % PRIME_MOD + PRIME_MOD) * PRIME_MULT + B[i]) % PRIME_MOD;
		if (hashA == hashB) countIfMatch(i-lenA+1);
	}
	printf("%d\n", matches);
	for (int i=0;i<matches;i++) {
		printf("%d ",indices[i]);
	}
	printf("\n");	
	return 0;
}