#include<stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <string.h> // for memcpy
#include <functional> // for not_equal_to
#include <math.h>
#include <limits.h>

using std::vector;

template < typename T, class Seq , class NotEq >
	void NaiveMatcher (Seq &data, Seq &pat, bool *tr , int n,int m)
	{
 		NotEq neq;
// 		int r=n-m;
		int s=0;
		typename Seq::iterator pIt;
		typename Seq::iterator endIt=pat.end();
		typename Seq::iterator dIt;
		typename Seq::iterator dEnd;
		typename Seq::iterator pBeg=pat.begin();
		typename Seq::iterator dBeg=data.begin();
		do
		{
			dIt=dBeg+s;
			dEnd=dIt+m;
			pIt=pBeg;
			while (pIt!=endIt)
			{
				if ( neq(*pIt,*dIt) )
				{
					
					tr[s]=false;
					break;
				}
				pIt++;
				dIt++;
			}
			s++;
		}
		while (dEnd!=data.end());
	}


template < typename T, class NotEq >
	void NaiveMatcher2 (T* data, T* pat, bool *tr , int n,int m)
	{
 		NotEq neq;
		int r=n-m;
		for (int s=0;s<r;s++)
		{
			for (int i=0;i<m;i++)
			
			{
				if ( neq(pat[i],data[s+i]) )
				{
					
					tr[s]=false;
					break;
				}
			}
		}
	}


void NM (int* d, int *p, bool *tr,int m,int n)
{
	int r=n-m;
	for (int s=0;s<r;s++)
	{
		for (int i=0;i<m;i++)
		{
			if (p[i]!=d[s+i])
			{
				tr[s]=false;
				break;
			}
		}
	}
}

void RKM (int*d,int*p,bool *tr, int m, int n, int q, int o,int h)
{
// 	int h=static_cast<int>(pow(o,m-1)) % q;
	int pt=0;
	int t0=0;
	int r=n-m;
	for (int i=0;i<m;i++)
	{
		pt=(o*pt + p[i])%q;
		t0=(o*t0 + d[i])%q; 
	}
	
	for (int s=0;s<r;s++)
	{
		if (pt==t0)
			for (int i=0;i<m;i++)
			{
				if (p[i]!=d[s+i])
				{
					tr[s]=false;
					break;
				}
			}
		else
			tr[s]=false;
// 		if (s<r)
			t0=(o*(t0 - d[s+1]*h) + d[s+m+1]) %q;
	}

}




void writeResults (const char * fl,bool * tr, int r)
{
	FILE *fp=fopen(fl,"w+");
	for (int i=0;i<r;i++)
	{
		fprintf (fp,"TR[%d]=%d\n",i,tr[i]);
		tr[i] = true;
	}
	fclose(fp);
}

int main(int argc, char* argv[])
{
	int n,m,d,s;
	FILE *fp;
	if (argc < 2)
	{	
		printf("Size of the text\n");
		scanf ("%d",&n);
		printf("Size of the pattern\n");
		scanf ("%d",&m);
		printf("Size of the alphabet\n");
		scanf ("%d",&d);
		printf("The move\n");
		scanf ("%d",&s);
	}
	else
	{
		fp=fopen(argv[1],"r");
		fscanf(fp,"%d %d %d %d",&n,&m,&d,&s);
		fclose(fp);
	}
	
	int r=n-m;
	if (r<0 || n <=0 || m<0 || d < 0 || s < 0 || s>=r)
	{
		printf("Invalid data\n");
		return -1;
	}
	
	int *T=new int[n], *P=new int[m];
	bool *TR=new bool[r];
	
	srand(time(NULL));
	for (int i=0;i<n;i++)
	{
		T[i] = static_cast<int> (static_cast<double> (d) * ( rand() / (RAND_MAX + 1.0)));
// 		printf ("T[%d]=%d\n",i,T[i]);
	}
	for (int i=0;i<r;i++)
		TR[i] = true;

	for (int i=0;i<m;i++)
		P[i]=T[s+i];
		
// 	for (int i=0;i<m;i++)
// 		printf("P[%d]=%d\n",i,P[i]);
	
	vector<int> T1 (T,T+n), P1 (P,P+m);
	struct timeval s1, s2;
	
	gettimeofday (&s1, NULL);
	NaiveMatcher<int, vector<int>, std::not_equal_to<int> >(T1,P1,TR,n,m);
	gettimeofday (&s2, NULL);
	printf ("NM: templated time %ld mikrosekund\n", s2.tv_usec - s1.tv_usec + (s2.tv_sec - s1.tv_sec) * 1000000);
	writeResults("result-NM-t",TR,r);

	gettimeofday (&s1, NULL);
	NaiveMatcher2<int, std::not_equal_to<int> >(T,P,TR,n,m);
	gettimeofday (&s2, NULL);
	printf ("NM: templated without stl time %ld mikrosekund\n", s2.tv_usec - s1.tv_usec + (s2.tv_sec - s1.tv_sec) * 1000000);
	writeResults("result-NM-t",TR,r);

	gettimeofday (&s1, NULL);
	NM(T,P,TR,m,n);
	gettimeofday (&s2, NULL);
	printf ("NM: c function time %ld mikrosekund\n", s2.tv_usec - s1.tv_usec + (s2.tv_sec - s1.tv_sec) * 1000000);
	
	writeResults("result-NM",TR,r);
	
	int q=INT_MAX/d;
	int h=static_cast<int>(pow(d,m-1)) % q;
	gettimeofday (&s1, NULL);
	RKM(T,P,TR,m,n,q,d,h);
	gettimeofday (&s2, NULL);
	printf ("RKM: c function time %ld mikrosekund\n", s2.tv_usec - s1.tv_usec + (s2.tv_sec - s1.tv_sec) * 1000000);
	
	writeResults("result-RKM",TR,r);

	delete [] T;
	delete [] TR;
	delete [] P;
	return 0;
}