# Horspool string search algorithm.

def search(pattern, text):
    print ("pattern =", pattern)
    print ("text =", text)
 
    n = len(text)
    m = len(pattern)
    shiftTable = [m]*128
    populateShiftTable(shiftTable, pattern, m-1)

    i = m -1
    while i < n:
        printLineup(pattern, text, i)
        k = 0
        while k < m and pattern[m-1-k]==text[i-k]:
            k += 1;
        if k==m:
            return i - m + 1
        i += shiftTable[ord(text[i])]
    return -1

def populateShiftTable(table, pattern, mMinusOne):
    for i in range(mMinusOne):
        table[ord(pattern[i])] = mMinusOne - i
    print ("shift table = ", end="")
    for c in pattern:
        print (c + str(table[ord(c)]), end=" ")
    print ("x" + str(table[ord("x")]), end=" ")
    print ()

def printLineup(pattern, text, i):
    print (text)
    print (" "*(i - len(pattern) + 1) + pattern)
    

print (search("ab", "abc"))
print (search("ab", "aabc"))
print (search("ab", "acabc"))
print (search("abd", "acabc"))
print (search ("abracadabra", "abracadabtabradabracadabcadaxbrabbracadabraxxxxxxabracadabracadabra"))