Cod sursa(job #303724)

Utilizator laserbeamBalan Catalin laserbeam Data 10 aprilie 2009 11:44:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<cstdio>
#include<cstring>
#define NMAX 2000003
#define mod1 100003
#define mod2 300007
#define base 135
using namespace std;
char A[NMAX],B[NMAX];
int poz[NMAX],e1,e2,hshA1,hshB1,hshA2,hshB2,i,nA,nB,nr;
int main()
{
	FILE *f = fopen("strmatch.in","r");
	fgets(A,sizeof(A),f);
	fgets(B,sizeof(B),f);
	fclose(f);
	nA = strlen(A);
	nB = strlen(B);
	A[--nA] = 0;
	B[--nB] = 0;
	hshA1 = hshA2 = A[0];
	hshB1 = hshB2 = B[0];
	e1 = e2 = 1;
	FILE *g = fopen("strmatch.out","w");
	if (nA > nB)
	{
		fprintf(g,"0\n");
		fclose(g);
		return 0;
	}
	for (i = 1; i < nA; ++i)
	{
		hshA1 = (hshA1 * base + A[i])%mod1;
		hshA2 = (hshA2 * base + A[i])%mod2;
		hshB1 = (hshB1 * base + B[i])%mod1;
		hshB2 = (hshB2 * base + B[i])%mod2;
		e1 = (e1 * base) % mod1;
		e2 = (e2 * base) % mod2;
	}
	nr = 0;
	if (hshA1 == hshB1 && hshA2 == hshB2)
	{
		poz[++nr] = 0;
	}
	for (i = nA; i < nB; ++i)
	{
		hshB1 = ((hshB1 - (B[i-nA] * e1)%mod1 + mod1) * base + B[i]) % mod1;
		hshB2 = ((hshB2 - (B[i-nA] * e2)%mod2 + mod2) * base + B[i]) % mod2;
		if (hshA1 == hshB1 && hshA2 == hshB2)
		{
			poz[++nr] = i-nA+1;
		}
	}
	fprintf(g,"%d\n",nr);
	for (i = 1; i <= nr && i <= 1000; ++i)
	{
		fprintf(g,"%d ",poz[i]);
	}
	fprintf(g,"\n");
	fclose(g);

return 0;
}