-
Notifications
You must be signed in to change notification settings - Fork 5
/
rabin-krap.py
47 lines (37 loc) · 1.59 KB
/
rabin-krap.py
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
"""
This file demonstrates the rabin krap string matching algorithm
"""
class RabinKarp:
def __init__(self,data):
self.data = data
def create_hash(self,pattern):
hash_array = [ord(char)*(256**index) for index,char in enumerate(list(pattern[::-1]))]
hash_array.reverse()
return hash_array
def search(self,pattern):
pattern_hash = sum(self.create_hash(pattern))
current_hash = None
for i in range(0,len(self.data)-len(pattern)):
if not current_hash:
current_hash = self.create_hash(self.data[i:len(pattern)])
print(current_hash)
else:
current_hash.pop(0)
#print("appending {}".format(self.data[i+len(pattern)-1]))
current_hash = [element*256 for element in current_hash]
current_hash.append(ord(self.data[i+len(pattern)-1]))
if pattern_hash == sum(current_hash):
print("Pattern Matched")
break
else:
print("not found")
def main():
algorithm = RabinKarp("""sdlkflsdjflksdjflksdjflksdjf
sdfklsdlfkjsdlkfjsdf
sdflksdklfjsldkfjlksdjf
sdflksdlkfjsdlkfjklsdhshubhams;dfs;dfjlksdfjlksdjflkadjsfuwejlfnsd;fj'asdjf;lasdjf;lweiufoisldvnhowirgegholer
vliarehifk;wejigerjslk.ghelrnvkljl;mskdvghlqeam;ewajksdv;kigwrjg
sdlikakdvmj;poqw4fe;dmjfiieam.vwrjiwmal/sfj;wevqaejgqeam';fwkp;vmeqal;'f
ewlfj;smv;oqefm'qlewolwjf;weamvng;kwejf'lqwaefmk;owgkvne;fjql/mvfliw4jg""")
algorithm.search("shubham")
main()