# https://gist.github.com/ameerkat/626643

# Boyer Moore String Search implementation in Python
# Written by:
# Ameer Ayoub <ameer.ayoub@gmail.com>
# Thanks Ameer!

# For a detailed description of what this algorithm is all about, go to
# https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
# or check out the long_BM_search.py file in this directory.

# Generate the Bad Character Skip List
def generateBadCharShift(term):
    skipList = {}
    for i in range(0, len(term)-1):
        skipList[term[i]] = len(term) - i-1
    return skipList

# Generate the Good Suffix Skip List
def findSuffixPosition(badchar, suffix, full_term):
    for offset in range(1, len(full_term)+1)[::-1]:
        flag = True
        for suffix_index in range(0, len(suffix)):
            term_index = offset - len(suffix)-1 + suffix_index
            if term_index < 0 or suffix[suffix_index] == full_term[term_index]:
                pass
            else:
                flag = False
        term_index = offset - len(suffix)-1
        if flag and (term_index <= 0 or full_term[term_index-1] != badchar):
            return len(full_term) - offset+1

def generateSuffixShift(key):
    skipList = {}
    buffer = ""
    for i in range(0, len(key)):
        skipList[len(buffer)] = findSuffixPosition(key[len(key)-1 - i], buffer, key)
        buffer = key[len(key)-1 - i] + buffer
    return skipList

# Now we get to the actual search algorithm
def BMSearch(haystack, needle):
    goodSuffix = generateSuffixShift(needle)
    badChar = generateBadCharShift(needle)
    i = 0
    while i < len(haystack) - len(needle)+1:
        j = len(needle)
        while j > 0 and needle[j-1] == haystack[i + j-1]:
            j -= 1
        if j > 0:
            badCharShift = badChar.get(haystack[i + j-1], len(needle))
            goodSuffixShift = goodSuffix[len(needle) - j]
            if badCharShift > goodSuffixShift:
                i += badCharShift
            else:
                i += goodSuffixShift
        else:
            return i
    return -1  # No match -- last resort


if __name__=="__main__":
    block = "This is a simple example"
    print("This is an example search on the string \"", block, "\".")
    print("ple :", BMSearch(block, "ple "))
    print("example :", BMSearch(block, "example"))
    print("simple :", BMSearch(block, "simple"))
    print(" imple :", BMSearch(block, " imple "))
