Finding a specific pattern in a text using the Knuth Morris Pratt pattern searching algorithm

KMP.py

def kmp(txt, pat):
    # base conditions
    if len(pat) == len(txt):
        if pat == txt:
            return 0
        else:
            return -1
    if len(pat) > len(txt):
        return -1
    if len(pat) == 0 or len(txt) == 0:
        return -1

    # making the lps array start
    lps = [0 for i in range(len(pat))]
    i = 1
    m = 0
    while i < len(pat):
        if pat[i] == pat[m]:
            m += 1
            lps[i] = m
            i += 1
        else:  # pat[i] != pat[m]
            if m != 0:
                m = lps[m-1]
            else:  # m == 0
                lps[i] = m
                i += 1
    # making the lps array end

    # kmp algo start
    x = 0
    y = 0

    while x < len(txt):
        if txt[x] == pat[y]:
            x += 1
            y += 1

            if y == len(pat):  # this means pattern found
                # y chars are already matched 
                # hence the starting index of the string is y chars behind x
                # so must return x-y
                return x-y

        else:  # txt[x] != pat[y]
            if y != 0:  
                y = lps[y-1]  # no need to move to the beginning of pattern as some already matches
            else:
                x += 1

    return -1
    # kmp algo end