FilesExpand file tree

 master

/

rabinkarp.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (46 loc) · 1.56 KB

 master

/

rabinkarp.py

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (46 loc) · 1.56 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

#Rabin Karp algorithm

# Java code https://github.com/mission-peace/interview/blob/master/src/com/interview/string/RabinKarpSearch.java

prime = 101

def pattern_matching(text, pattern):

m = len(pattern)

n = len(text)

pattern_hash = create_hash(pattern, m - 1)

text_hash = create_hash(text, m - 1)

for i in range(1, n - m + 2):

if pattern_hash == text_hash:

if check_equal(text[i-1:i+m-1], pattern[0:]) is True:

return i - 1;

if i < n - m + 1:

text_hash = recalculate_hash(text, i-1, i+m-1, text_hash, m)

return -1;

def check_equal(str1, str2):

if len(str1) != len(str2):

return False;

i = 0

j = 0

for i, j in zip(str1, str2):

if i != j:

return False;

return True

def create_hash(input, end):

hash = 0

for i in range(end + 1):

hash = hash + ord(input[i])*pow(prime, i)

return hash

def recalculate_hash(input, old_index, new_index, old_hash, pattern_len):

new_hash = old_hash - ord(input[old_index])

new_hash = new_hash/prime

new_hash += ord(input[new_index])*pow(prime, pattern_len - 1)

return new_hash;

index = pattern_matching("TusharRoy", "sharRoy")

print("Index ", index)

index = pattern_matching("TusharRoy", "Roy")

print("Index ", index)

index = pattern_matching("TusharRoy", "shar")

print("Index ", index)

index = pattern_matching("TusharRoy", "usha")

print("Index ", index)

index = pattern_matching("TusharRoy", "Tus")

print("Index ", index)

index = pattern_matching("TusharRoy", "Roa")

print("Index ", index)