Cod sursa(job #340384)

Utilizator Mishu91Andrei Misarca Mishu91 Data 14 august 2009 14:04:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <cstring>

#define MAX_N 2000005
#define MOD1 100007
#define MOD2 100021
#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, H1 = 0, h2 = 0, H2 = 0, P1 = 1, P2 = 1;
	for(int i = 0; i < N; ++i)
	{
		h1 = (h1*P + A[i]) % MOD1;
		h2 = (h2*P + A[i]) % MOD2;
		H1 = (H1*P + B[i]) % MOD1;
		H2 = (H2*P + B[i]) % MOD2;
		if(i)
			P1 = (P1 * P) % MOD1,
			P2 = (P2 * P) % MOD2;
	}
	
	if(H1 == h1 && H2 == h2)
		match[++nrm] = 0;
	
	for(int i = N; i < M; ++i)
	{
		H1 = ((H1 - (B[i-N]*P1) % MOD1 + MOD1)*P + B[i]) % MOD1;
		H2 = ((H2 - (B[i-N]*P2) % MOD2 + MOD2)*P + B[i]) % MOD2;	
		if(H1 == h1 && H2 == h2)
			match[++nrm] = i - N + 1;
	}
	
	printf("%d\n",nrm);
	
	for(int i = 1; i <= nrm && i <= 1000; ++i)
		printf("%d ", match[i]);
}