Cod sursa(job #332341)

Utilizator AnDrEwBoYA Andrei AnDrEwBoY Data 17 iulie 2009 15:31:13
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
#include<string>

#define base 73
#define M1 100007
#define M2 100021

#define MAX_N 2000010

char A[MAX_N],B[MAX_N];
int n,m,sol[1001],total;

void read(),solve(),show();

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	read();
	solve();
	show();
	
	fclose(stdin); fclose(stdout);
}

void read()
{
   scanf("%s %s",A,B);
   m = strlen(A);
   n = strlen(B);
}

void solve()
{
	unsigned int hashA1,hashA2;
	unsigned int H1,H2,i;
	unsigned int hashB1,hashB2;
	
	H1 = H2 = 1;
	hashA1 = hashA2 = hashB1 = hashB2 = 0;
	for(i = 0; i < m; i++)
	{
		hashA1 = (hashA1 * base + A[i]) % M1;
		hashA2 = (hashA2 * base + A[i]) % M2;
		
		hashB1 = (hashB1 * base + B[i]) % M1;
		hashB2 = (hashB2 * base + B[i]) % M2;
		
		if(!i) continue;
		H1 = (H1 * base) % M1;
		H2 = (H2 * base) % M2;
	}
	
	for(i = 0; i <= n-m; i++)
	{
		if(hashA1 == hashB1 && hashA2 == hashB2)
		{
			if(total < 1000) sol[total++] = i; else total++;
		}
		hashB1 = ((hashB1 - (B[i] * H1) % M1 + M1) * base + B[i+m]) % M1;
		hashB2 = ((hashB2 - (B[i] * H2) % M2 + M2) * base + B[i+m]) % M2;
	}
}

void show()
{
	printf("%d\n",total);
	for(int i = 0; i < (total < 1000 ? total : 1000); i++)
		printf("%d ",sol[i]);
}