KMP方法

KMP是一种字符串搜索算法。网络上查到的2种算法都存在bug，对于“aaa"这种特殊情况会出现错误或者死循环。
下面是改进的方法：

def build_patter(s):
    n = len(s)
    next = [0]*n
    i = 1
    j = 0
    while i < n:
        if j == 0 and s[i] != s[j]:
            next[i]=0
            i += 1
        elif j !=0 and s[i] !=s[j]:
            j = next[j-1]
        elif s[j] == s[i]:
            j+=1
            next[i]=j
            i+=1
    return next
def kmp(p,s):
    if s == "":
        return -1
    next = build_patter(s)
    p_len = len(p)
    s_len = len(s)
    i = j = 0
    while i < p_len:
        if p[i] == s[j]:
            i +=1
            j +=1
            if j >=s_len:
                return i - s_len
        elif next[j] == 0:
            i+=1
            j = 0
        else:
            j = next[j-1]

    return -1
print(kmp("asdassaaababababcabcfffj","abab"))