Cod sursa(job #340377)

Utilizator Mishu91Andrei Misarca Mishu91 Data 14 august 2009 13:55:24
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <cstring>

#define MAX_N 2000005
#define MOD 100007
#define P 73

int match[MAX_N], nrm;
char A[MAX_N], B[MAX_N];

int main()
{
	freopen("strmatch.in","rt",stdin);
	freopen("strmatch.out","wt",stdout);
	
	scanf("%s\n%s",A, B);
	int N = strlen(A);
	int M = strlen(B);
	
	int h1 = 0, P1 = 1, H1 = 0;
	for(int i = 0; i < N; ++i)
	{
		h1 = (h1*P + A[i]) % MOD;
		H1 = (H1*P + B[i]) % MOD;
		if(i)
			P1 = (P1 * P) % MOD;
	}
	
	if(H1 == h1)
		match[++nrm] = 1;
	
	//fprintf(stderr, "%d %d\n", h1, H1);
	
	for(int i = N; i < M; ++i)
	{
		H1 = ((H1 - (B[i-N]*P1) % MOD + MOD)*P + B[i]) % MOD;
		if(H1 == h1)
			match[++nrm] = i - N + 1;
		//fprintf(stderr,"%d ",H1);
	}
	
	printf("%d\n",nrm);
	
	for(int i = 1; i <= nrm && i <= 1000; ++i)
		printf("%d ", match[i]);
}