Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
def index_of(text, pattern):
assert isinstance(text, str), 'text is not a string: {}'.format(text)
assert isinstance(pattern, str), 'pattern is not a string: {}'.format(text)
"""In the Boyer-Moore algorithm, you start comparing pattern characters to text characters from the end of the pattern.
If you find a mismatch, you have a configuration of the type"""
# Check if empty; if so, return 0, earliest bit
# Use the shift rule according to boyer-moore
if len(pattern) == 0:
return 0
pattern = list(pattern)
pattern_len = len(pattern)
text = list(text)
textext_len = len(text)
shift = 0
while(shift <= textext_len - pattern_len):
index = pattern_len - 1
# Keep going until it all meets
while index >= 0 and pattern[index] == text[shift+index]:
index -= 1
# If we get past index, then return where the shift is
if index < 0:
return shift
if text[shift+pattern_len-1] in pattern:
shift += pattern_len - pattern.index(text[shift+pattern_len-1]) - 1
shift += pattern_len
return None
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.