index_of.py

boyes_moore_index_of.py

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
        else:
            if text[shift+pattern_len-1] in pattern:
                shift += pattern_len - pattern.index(text[shift+pattern_len-1]) - 1
            else:
                shift += pattern_len
    return None