Cod sursa(job #564278)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 27 martie 2011 00:36:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<fstream>
#include<string.h>
using namespace std;
fstream f1,f2;
char A[2000002];
char B[2000002];
int P1,P2,i,hA1,hA2,hB1,hB2,M,N,k,x[2000002];
int nextHash1(int v, char x, char y)
{
	v=((v-(P1*x)%100019+100019)*73+y)%100019;
	return v;
}
int nextHash2(int v, char x, char y)
{
	v=((v-(P2*x)%100023+100023)*73+y)%100023;
	return v;
}

int main()
{
	f1.open("strmatch.in",ios::in);
	f2.open("strmatch.out",ios::out);
	f1>>A>>B;
	M=strlen(A);
	N=strlen(B);
	hA1=0; hA2=0; hB1=0; hB2=0; P1=1; P2=1;
	//initializarea hashurilor
	for (i=0;i<M;i++)
	{
		hA1=(hA1*73+A[i])%100019;
		hA2=(hA2*73+A[i])%100023;
		hB1=(hB1*73+B[i])%100019;
		hB2=(hB2*73+B[i])%100023;
		if (i)P1=(P1*73)%100019;
		if (i)P2=(P2*73)%100023;
	}
	k=0;
	if (hA1==hB1 && hA2==hB2){x[k]=0;k++;}
	for (i=M;i<N;i++)
	{
		hB1=nextHash1(hB1,B[i-M],B[i]);
		hB2=nextHash2(hB2,B[i-M],B[i]);
		if (hA1==hB1 && hA2==hB2){x[k]=i-M+1;k++;}
	}
	f2<<k<<"\n";
	for (i=0;i<k && i<1000;i++) f2<<x[i]<<" ";
	f2.close();
	f1.close();
	return 0;
}