-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsubstringSearch.cpp
More file actions
122 lines (101 loc) · 3.29 KB
/
substringSearch.cpp
File metadata and controls
122 lines (101 loc) · 3.29 KB
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// /*----------------------------------------------------------------------------------------------------*/
// //************************* Substring Search using Rolling Hash *********************
//
// * Language used- C++
// * Function Used-
// * Data Structure RollingHash
// -----------------------------------------------------------------------------------------------------------------------*/
#include<bits/stdc++.h>
using namespace std;
int RandomPrime=7129;
//-----------------------------------class declaration of random hash ---------------------
class RollingHash{
public:
long long int value;
int hash;
int plus;
RollingHash()
:value(0),hash(0),plus(0){
cout<<"hash created"<<endl;
};
void append(const char& c){
value=value*7+((int)c-96);
hash=value%RandomPrime;
plus++;
};
void skip(const char& c){
value-=((int)c-96)*powF(7,plus-1);
hash=value%RandomPrime;
plus--;
};
friend bool operator==(const RollingHash& r1,const RollingHash& r2){
if(r1.hash==r2.hash)
return true;
return false;
}
int powF(int x,int y){
int power{1};
while(y--)
power*=x;
return power;
}
};
//----------------end of classs------------------------//
int main(){
string s;
string t="cissurelyabeautifullanguageformeUnfortunatelycsbeautyisnotinitssyntaxorinitscodingstyleItliesinitscoremanydeveloperswhofallinlovewiththislanguageonce";
cout<<"Enter the string u want to serach"<<endl;
cin>>s;
int sLength=s.length();
// declaring two rolling hash objects
RollingHash rs,rt;
for(auto& x:s)
rs.append(x);
for(int i{0};i<sLength;i++)
rt.append(t[i]);
cout<<rs.plus<<" "<<rs.value<<" "<<rs.hash<<endl;
cout<<"-----------------------------\n";
cout<<rt.plus<<" "<<rt.value<<" "<<rt.hash<<endl;
int i;
//Karp-Rabin------------------------------------
for(i=1;i<t.length()-sLength;i++){
if(rt==rs){
int x=i-1;
int j=0;
while(j<sLength){
if(t[x]!=s[j]){
cout<<"failed\n";
}
j++;
x++;
}
if(j==sLength){
cout<<"\n--------------------------------------------------------------------\n";
cout<<"String Found!!!\n";
sLength+=i;
i=i-1;
while(i<sLength-1){
cout<<t[i]<<" ";
i++;
}
cout<<"\n";
cout<<"-------------------------------------------------------------------\n";
break;
}
}
rt.append(t[i+sLength-1]);
rt.skip(t[i-1]);
cout<<rs.plus<<" "<<rs.value<<" "<<rs.hash<<endl;
cout<<"-----------------------------\n";
cout<<rt.plus<<" "<<rt.value<<" "<<rt.hash<<endl;
}
if(i==t.length()){
cout<<" \n string Not Found \n";
}
// sLength+=i;
// while(i<sLength-1){
// cout<<t[i]<<" ";
// i++;
// }
return 0;
}