KMP算法（python）
KMP算法（python）
(1)暴力搜索算法
作者：野指针S-E
复杂度：O（m*n）
def strMacth(t,p):
m,n=len(t),len(p)
i,j=0,0
while i<m and j<n:
if p[j]==t[i]:
j,i=j+1,i+1
else:
j,i=0,i-j+1
if j==n:
return i-j
else:
return -1
t="ababcabcacbab"
p="abcac"
x=strMacth(t,p)
print(x)
#结果：5
(2)算法
（2.1）求解pnext表的过程:
去掉尾部一行并在头部前面添加-1，得到：
复杂度：O（n）
def gen_pnext(p):
#生成针对p中各位置i的下一检查位置函数，用于KMP算法
i,k,m=0,-1,len(p)
pnext=[-1]*m #初始数组全部元素为-1
while i<m-1: #生成下一个pnext元素值
if k==-1 or p[i]==p[k]:
i,k=i+1,k+1
pnext[i]=k #设置pnext元素
else:
k=pnext[k] #退回更短相同前缀
return pnext
def KMP(t,p,pnext):
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
t="ababcabcacbab"
p="abcac"
pnext=gen_pnext(p)
x=KMP(t,p,pnext)
print(x)
#结果：5
作者：野指针S-E
