Skip to content

Instantly share code, notes, and snippets.

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
if skip == 0:
print "Found at {0}".format(i)
i += skip
print "Not Found"
Copy link

Lazaruz00 commented Sep 10, 2020

why in range, the number is specified as 256?

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