KMP算法

看毛片算法的具体细节：详解
主字符为：m, 查找字符为：n
该算法用于字符匹配，时间复杂度为O（m+n），空间复杂度为：O（n）
我这里准备实现一个python3版的代码。
考虑到对于next的实现有些复杂，这里附上讲解

# KMP
def next_kmp(nums):
    next_list = [-1]
    i = 0
    j = next_list[0]
    while i < len(nums)-1:
        if j == -1 or nums[i] == nums[j]:
            i += 1
            j += 1
            next_list.append(j)
        else:
            j = next_list[j]
    return next_list

def kmp(long_str, short_str):
    next_list = next_kmp(short_str)
    start = 0
    short_location = 0
    while start < len(long_str):
        if long_str[start] == short_str[short_location] or short_location == -1:
            start += 1
            short_location += 1

            if short_location == len(short_str):
                return start - short_location
        else:
            short_location = next_list[short_location]

    return False

test = "abcabcabdabab"
lo = kmp(test, 'abab')
print(lo)