Cod sursa(job #773043)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 31 iulie 2012 20:19:07
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[2000010];
char B[2000010];

int P = 79, n;
int MOD = 31179;
int mod = 30117;

int HA, ha, HB, hb, nr, v[1010], da, p, pa, i, q, qa;

int main() {
	f>>A;
	f>>B;
	n=strlen(B)-strlen(A)-1;
	//construiesc codurile hash asociat lui A = (A[0]*p^0 + A[1]*p^1 + ...) % MOD
	
	int da = strlen(A);
	p = q = 1;
	for (i=0;A[i]!=0;i++) {
		HA = (HA + (p*A[da-i-1]) % MOD) % MOD;
		ha = (ha + (q*A[da-i-1]) % mod) % mod;
		//construiesc odata cu codurile hash ale lui A si codurile hash ale primei secvente de lungime lenA din B
		HB = (HB + (p*B[da-i-1]) % MOD) % MOD;
		hb = (hb + (q*B[da-i-1]) % mod) % mod;
		pa = p;
		qa = q;
		p = (p * P) % MOD;
		q = (q * P) % mod;
	}
	
	if (HA == HB && ha == hb)
		v[++nr]=0;
	
	for(i=1; i<=n; i++)
	{
		HB = (((HB - (B[i-1] * pa) % MOD + MOD) % MOD ) * P + B[i+da-1]) % MOD;
		hb = (((hb - (B[i-1] * qa) % mod + mod) % mod ) * P + B[i+da-1]) % mod;
		if (HA == HB && ha == hb) {
			v[++nr]=i;
			if (nr > 1000) {
				nr --;
				break;
			}
		}
		
	}
	g<<nr<<"\n";
	for (i=1;i<=nr;i++) {
		g<<v[i] << " ";
	}
	g<<"\n";
}