Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Boyer-Moore-Horspool Python implementation
class BoyerMoore:
def __init__(self, text, pattern):
self.text = text
self.pattern = pattern
self.m = len(pattern)
self.n = len(text)
self.skip = []
for i in range(256): self.skip.append(-1)
for i in range(self.m): self.skip[ord(pattern[i])] = self.m
def search(self):
for i in range(self.n + self.m + 1):
skip = 0
for j in range(self.m-1, -1, -1):
if self.text[i+j] != self.pattern[j]:
skip = j - self.skip[ord(self.text[i+j])]
if skip < 1: skip = 1
break
if skip == 0:
print "Found at {0}".format(i)
return
i += skip
print "Not Found"
return
@pforderique
Copy link

pforderique commented Apr 9, 2021

why in range, the number is specified as 256?

Hi Lazaruz00,
I believe that instead of using a hashing implementation of the "bad match table" with a dictionary, this implementation instead uses a direct access array for all 256 ASCII characters and places them using the ord() function.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment