Cod sursa(job #530096)

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

#define MAXN 2000001
#define MAX_MATCHES 1001
#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 = A[0]%PRIME_MOD; hashB = B[0]%PRIME_MOD; pow = 1;
	for (int i = 1; i < lenA; i++)	{
		hashA = (hashA * PRIME_MULT + A[i]) % PRIME_MOD;
		hashB = (hashB * PRIME_MULT + B[i]) % PRIME_MOD;
		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=1;i<=matches;i++) {
		printf("%d ",indices[i]);
	}
	printf("\n");	
	return 0;
}