cppsolutions/RabinKarp.cpp at master · ananddeb23/cppsolutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<vector>
#include<string.h>
#include<math.h>
using namespace std;
long hashpt( char pt[]){
	long l=strlen(pt);
	long hsh=0;
	for(long x=0;x<l;x++){
		hsh+=pt[x]*((long)(pow(3,x)));

	}
	cout<<" Hash for "<<pt<<" is "<<hsh<<endl;
	return hsh;
}
long hashfirst(char txt[],long l){

	long hsh=0;
	for(long x=0;x<l;x++){
		hsh+=txt[x]*((long)(pow(3,x)));

	}
	cout<<" Hash for first m chars "<<" is "<<hsh<<endl;
	return hsh;
}
long nwhash(char n,long l,char old,long oldhash){
	long hash=oldhash-((long)(old));
	hash/=3;
	hash+=((long)(n))*((long)(pow(3,l-1)));

//	cout<<" New hash  "<<" is "<<hash<<endl;
	return hash;
}
int main(){
char pt[40];
char txt[200];
cin.getline(pt,40);
cin.getline(txt,200);
long hpt=hashpt(pt);
//cout<<" im here";
long hsh=hashfirst(txt,strlen(pt));
long l1=strlen(pt);
long l=strlen(txt);
long flag=0;
//cout<<" im here";
long calchash=hsh;
if(hsh==hpt){
for(long y=0;y<l1;y++){
	if(pt[y]!=txt[y]){
		flag=1;
		break;
	}
}
if(flag==0){
	cout <<"Found at index: 0"<<endl;;
			return 0;
}

}

for(long x=1;x<l-l1+1;x++){
	hsh=nwhash(txt[x+l1-1],strlen(pt),txt[x-1],calchash);
	calchash=hsh;
	cout<<" Hash for ";
	for(long j=x;j<=x+l1-1;j++){
		cout<<txt[j];
	}
	cout<<" is "<<hsh<<endl;
	if(hsh==hpt){
		flag=0;
		for(long y=0;y<l1;y++){
			if(pt[y]!=txt[x+y]){
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			cout <<"Found at index: "<<x<<endl;;
			return 0;
		}
	}
}
cout<<"Not found\n";
return 0;
}