python的KMP算法实现
##算法的复杂度为O(n)
def matching_KMP(t, p, pnext):
'''KMP串匹配，主函数'''
j, i = 0, 0
n, m = len(t), len(p)
while j < n and i < m:
if i == -1 or t[j] == p[i]:
j, i = j+1, i+1
else:
i = pnext[i]
if i == m:
return j-i
return -1
##算法复杂度为O(m)
def gen_pnext(p):
'''生成针对p中各位置i的下一检查位置表，用于KMP算法'''
i, k, m = 0, -1, len(p)
pnext = [-1 for i in range(m)]
while i < m-1:
if k == -1 or p[i] == p[k]:
i, k = i+1, k+1
if p[i] == p[k]:
pnext[i] = pnext[k]
else:
pnext[i] = k
else:
k = pnext[k]
return pnext
总的算法复杂度为O(m+n)，但是因为一般情况下匹配字符串的长度远远小于目标字符串，所以说，总的复杂度认为是O(n)。
