djurban

#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;		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;				}			}		}	}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;}