Boyer-Moore-Horspool String Searching Algorithm

BoyerMoore.py

#!usr/bin/py

# Boyer-Moore String Matching Algorithm

class BoyerMoore:
	def __init__(self, text, pattern):
		self.text = text
		self.pattern = pattern
		self.m = len(pattern)
		self.n = len(text)
		self.skip = []

		# Initialize skip table
		# It gives, for each character in the alphabet,
		# the index of its rightmost occurrence in the pattern
		# (or -1 if the character is not in the pattern).
		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


def main():
	text = "This is a test string"
	pattern = "test"
	bm = BoyerMoore(text, pattern)
	bm.search()

if __name__ == '__main__':
	main()