# Horspool

def search(pattern, text):
    """ return index of first occurrence of pattern in text; 
        return -1 if no match """
    n, m = len(text), len(pattern)
    shiftTable = [m]*128 # if char not in pattern, shift by full amount
    populateShiftTable(shiftTable, pattern, m-1)

    i = m - 1 # i is position in text that corresponds to end of pattern
    
    while i < n:  # while not past end of text
        k = 0 # k is number of pattern characters compared so far
        
        while k < m and pattern[m-1-k]==text[i-k]: 
            k += 1;  # loop stops if mismatch or complete match
            
        if k==m:  # found a match
            return i - m + 1  
        
        i += shiftTable[ord(text[i])] # ready to begin next comparison
    return -1

def populateShiftTable(table, pattern, mMinusOne):
    for i in range(mMinusOne):
        table[ord(pattern[i])] = mMinusOne - i
 
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"))