lsp array for kmp search

lps.py

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
            i += 1
        else:
            if current_len_of_lps != 0:
                current_len_of_lps = lps[current_len_of_lps-1]
            else:
                lps[i] = 0
                i += 1
    return lps


if __name__ == "__main__":
    print(gen_lps("ABABCABAB"))