// KarpRabin.cpp: implementation of the KarpRabin class.
//
//////////////////////////////////////////////////////////////////////

#include "KarpRabin.h"
#include <string.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

KarpRabin::KarpRabin()
{}

KarpRabin::~KarpRabin()
{}


void KarpRabin::test()
{
	TimeIt tt;
	KarpRabin kr;
	kr.search();
	kr.OUTPUT(tt.GetMSecElapsed());
}

#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))

void KarpRabin::search() 
{
	char *x = (char*)m_search,
		 *y = (char*)m_context;
	int m = strlen(m_search), 
		n = strlen(m_context);

	int d, hx, hy, i, j;

	/* Preprocessing */
	/* computes d = 2^(m-1) with
	the left-shift operator */
	for (d = i = 1; i < m; ++i)
		d = (d<<1);

	for (hy = hx = i = 0; i < m; ++i) {
		hx = ((hx<<1) + x[i]);
		hy = ((hy<<1) + y[i]);
	}

	/* Searching */
	j = 0;
	while (j <= n-m) {
		if (hx == hy && memcmp(x, y + j, m) == 0)
			OUTPUT(j);
		hy = REHASH(y[j], y[j + m], hy);
		++j;
	}
}