FilesExpand file tree

 master

/

rabin_karp.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

48 lines (39 loc) · 1.51 KB

 master

/

rabin_karp.py

Copy path

Top

File metadata and controls

• Code
• Blame

48 lines (39 loc) · 1.51 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

# Following program is the python implementation of

# Rabin Karp Algorithm

class RollingHash:

def __init__(self, text, sizeWord):

self.text = text

self.hash = 0

self.sizeWord = sizeWord

for i in range(0, sizeWord):

#ord maps the character to a number

#subtract out the ASCII value of "a" to start the indexing at zero

self.hash += (ord(self.text[i]) - ord("a")+1)*(26**(sizeWord - i -1))

#start index of current window

self.window_start = 0

#end of index window

self.window_end = sizeWord

def move_window(self):

if self.window_end <= len(self.text) - 1:

#remove left letter from hash value

self.hash -= (ord(self.text[self.window_start]) - ord("a")+1)*26**(self.sizeWord-1)

self.hash *= 26

self.hash += ord(self.text[self.window_end])- ord("a")+1

self.window_start += 1

self.window_end += 1

def window_text(self):

return self.text[self.window_start:self.window_end]

def rabin_karp(word, text):

if word == "" or text == "":

return None

if len(word) > len(text):

return None

rolling_hash = RollingHash(text, len(word))

word_hash = RollingHash(word, len(word))

#word_hash.move_window()

for i in range(len(text) - len(word) + 1):

if rolling_hash.hash == word_hash.hash:

if rolling_hash.window_text() == word:

return i

rolling_hash.move_window()

return None