#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const unsigned radix = 256;
const unsigned prime = 492853;

int rabin_karp(char *text, char *pattern)
{
	//lenghts
	int m = strlen(pattern);
	int n = strlen(text);

	//temporary buffer for 
	char *tmp = malloc(m+1);

	//radix^m-1
	unsigned long high = 1;

	//loop counters
	int i,j;

	//initialize high
	for(i = 0; i < m-1; i++)
	{
		high = (high * radix) % prime;
	}

	printf("high: %ld\n", high);

	//p - pattern hash
	//t - text window hash
	unsigned long p = 0;
	unsigned long t = 0;

	//compute pattern hash & first window hash
	for(i = 0; i < m; i++)
	{
		p = ((radix*p) + pattern[i]) % prime;
		t = ((radix*t) + text[i]) % prime;
	}

	printf("pattern hash: %ld\n", p);

	for(i = 0; i < n - m + 1; i++)
	{
		unsigned long testhash = 0;
		for(j = 0; j < m; j++){
			testhash = ((radix*testhash) + text[i+j]) % prime;
		}

		strncpy(tmp, text+i, m);
		printf("offset: %d, text: %s, hash: %ld, re-hash: %ld\n", i, tmp, t, testhash);

		if(p == t){
			if(!strncmp(text+i, pattern, m)){
				printf("match at %d\n", i);
			}else{
				strncpy(tmp, text+i, m);
				printf("spurious match with %s at %d\n", tmp, i);
			}
		}

		if(i < n - m){
			t = t - high*text[i];
			t = (radix*t + text[i+m]) % prime;
		}
	}

	return 0;
}

int main(void)
{
	char text[] = "2359023141526739921";
	char patt[] = "31415";

	rabin_karp(text,patt);

	return EXIT_SUCCESS;
}