rendered paste body#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;}