KMP算法python代码

问题：给定两个字符串a="sdfaabcddsdfssd",b="df"找出字串b在a中的下标位置。

朴素模式匹配算法:

def str_index(a,b,pos=0): i = pos j = 0 while i < len(a) and j < len(b): if a[i] == b[j]: j += 1 i += 1 else: i = i-j+1 j = 0 if j == len(b): return i-j else: return -1

KMP算法:需创建next_arr数组，存放b串中 每个下标位置前(不包含当前下标) 字符串的前缀和后缀相同的个数，作用是：在字符匹配失败时，判定应该继续从b串的哪一位字符开始继续匹配

def kmp_next(b): next_arr = [-1] * len(b) i = 0 j = -1 while i < len(b)-1: if j == -1 or b[j] == b[i]: i += 1 j += 1 next_arr[i] = j else: j = next_arr[j] return next_arr def kmp_index(a,b,pos=0): i = pos j = -1 kmp_next_arr = kmp_next(b) while i < len(a) and j < len(b): if j == -1 or a[i] == b[j]: i += 1 j += 1 else: j = kmp_next_arr[j] if j == len(b): return i - j else: return -1 if __name__ == '__main__': # index = str_index('sdfaabcddsdfssd','sdf',1) index = kmp_index('sdfaabcddsdfssd','df')

KMP的改进算法：修改了next_arr数组的获取方法。

主要逻辑：

1.假设b串中当前需要判断的位置下标为：k。

2.k位置下对应的 前字符串前后缀字符重复个数为：n,即next_arr[k]=n。

3.n位置下对应的 前字符串前后缀字符重复个数为：nn,即next_arr[n]=nn.

则判断b[k]与b[n]的值是否相同，若相同next_arr[k]=nn,若不同，下标k对应的值不变，还是next_arr[k] = n

def kmp_next_optimize(b): next_arr = [-1] * len(b) i = 0 j = -1 while i < len(b)-1: if j == -1 or b[j] == b[i]: i += 1 j += 1 if b[j] != b[i]: next_arr[i] = j else: next_arr[i] = next_arr[j] else: j = next_arr[j] return next_arr

若代码难以理解可参考博客：https://blog.csdn.net/v_JULY_v/article/details/7041827