KMP pattern search algorithm

kmp.py

from lps import gen_lps # reference lps.py


def kmp_search(pat, txt):
    N = len(txt)
    M = len(pat)
    lps = gen_lps(pat)
    print('here', lps)

    i, j = 0, 0
    while i < N:
        if pat[j] == txt[i]:
            j += 1
            i += 1
        if j == M:
            print(f'found at {i-M}')
            j = lps[j-1]
        if i < N and pat[j] != txt[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1


if __name__ == "__main__":
    txt = "ABABDABACDABABCABABddddddddABABCABABddABABCABAB"
    pat = "ABABCABAB"
    kmp_search(pat, txt)