An implementation of the Knuth-Morris-Pratt Algorithm

KMP.py

def table(sub):
    pos, cnd = 2, 0
    T = [-1,0]
    while pos < len(sub):
        if sub[pos-1] == sub[cnd]:
            cnd += 1
            pos += 1
            T.insert(pos,cnd)
        elif cnd > 0:
            cnd = T[cnd]
        else:
            T.insert(pos,0)
            pos += 1
    return T
def kmp(string,sub):
    m = i = 0
    T = table(sub)
    while m + i < len(string):
        if sub[i] == string[m + i]:
            if i == len(sub) - 1:
                return m
            i += 1
        else:
            m += i - T[i]
            if T[i] > -1:
                i = T[i]
            else:
                i = 0
    return -1