# KMP string search

# build the table that tells how many characters matched.
def populateTable(table, pattern):
    m= len(pattern)
    table[1] = 0
    current = 2
    candidatePosition = 0
    
    while current < m:
        if pattern[current-1] == pattern[candidatePosition]:
            candidatePosition += 1
            table[current] = candidatePosition
            current += 1
        elif candidatePosition > 0:
            candidatePosition = table[candidatePosition]
        else:
            table[current] = 0
            current += 1

# So we can see the shifts in action            
def printLineup(pattern, text, i):
    print (text)
    print (" "*(i) + pattern + "    " +(str(i)))



def search(pattern, text):
    print ("pattern =", pattern)
    print ("text =", text)
 
    n = len(text)
    m = len(pattern)
    print ("m = %d,  n = %d" %(m,n))
    table = [-1]*m # most of the -1's will be replaced.  shiftTable[0] will always be -1.
    populateTable(table, pattern)
    print (table)
    
    i=0
    k=0
    comparisons = 0
    
    
    while i + k < n:
        comparisons += 1
        if pattern[k] == text[i + k]:
            # print("if ", i, k)
            if k == m - 1:
                return i
            k += 1
        elif table[k] >= 0:
            # print("elif ", i, k, table[k])
            i = i + k - table[k]
            k = table[k]
            printLineup(pattern, text, i)
            
        else:
            # print("else ", i, k)
            k = 0
            i += 1
            printLineup(pattern, text, i)
            
    return -1
            
      

#print (search("ab", "abc"))
#print (search("ab", "aabc"))
#print (search("ab", "acabc"))
#print (search("abd", "acabc"))
#print (search("wowwow", "awowwow"))
# print (search("awowwow", "awow oh wow oh wowwow oh awow oh awowwowwow"))
# print (search("banana", "anna and nan in a cabana ate a banal  banana"))
#print (search ("abracadabra", "abracadabtabradabracadabcadaxbrabbracadabraxxxxxxabracadabracadabra"))
# print (search ("abcdcbcabcabc", "abracadabtabradabracadabcadaxbrabbracadabraxxxxxxabracadabracadabra"))
#print (search ("hollyholdsalcohol", "sallyholdsalcoholwhyodoeshollyholdalcohol?hollyholdsalcohol"))
#print (search("abcdcbcabcabc", "abc"))
#print(search("wowwow", "bracadaabrabadabraabracacabracadabracadabra"))
#print(search("banana", "bracadaabrabadabraabracacabracadabracadabra"))
#print(search("holdalcohol", "bracadaabrabadabraabracacabracadabracadabra"))
#print(search("APPLE APP", "BPPLE APPLEAAPPAPPAPPAPPLE PAPAPPLE APPLE APP"))
print (search ("participate in parachute", "apartyappisparticipating in partiesparticipate in parachuteparts"))