bdss58

def gen_lps(pat):
    M = len(pat)  # length of pat
    current_len_of_lps = 0  # length of the previous longest prefix suffix
    lps = [0]*M
    if M == 1:
        return lps
    for i in range(1, M):
        if pat[i] == pat[current_len_of_lps]:
            current_len_of_lps += 1
            lps[i] = current_len_of_lps

bdss58

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