kmp算法的总结
时间:5年前 阅读:4466
KMP算法我看了很多次,每次都觉得自己理解了,但是当返回头来用的时候,就又觉得不是很理解,今天我就把思路整理一下好了:
KMP算法主要有两个部分
1、计算next前缀函数,其实就是一个数组,每个元素储存了如果模式串和Target串在改点匹配不成功时,应该将模式串的那个点与之匹配。
2、实现模式串匹配
1、计算前缀函数:
该函数的基本思想是,找到某一点i前面(包含该点)前缀等于后缀的最大长度:举例:a b a a b a,其中设初始next[1] = 0,next[2]怎么算呢?包括下面几种情况,如果a[2]==a[1],那么next[2] = 1;如果a[2]!= a[1],证明前缀等于后缀的个数为0,那么next[2]=k=0;
next[3]呢?因为要找前缀和后缀,如果前面已经匹配了a[1],则匹配a[2],如果前面没有匹配a[1],那么就只能从头匹配a[1],在此例中,因为next[2]=0,意味着a[2]未与T匹配,故继续从头匹配。因为a[3]==a[1],next[3]=k=1;
next[4]呢?正如前面所述,由于next[3]>0,故a[3]已经与T匹配了k个,则a[4]需要和a[k+1]进行匹配,即a[2],由于未匹配成功,故需要继续往前匹配,即a[1],匹配成功,则next[4] = k = 1;
next[5]呢?正如前面所述,由于next[4]>0,故a[4]已经与T匹配了k个,则a[5]需要和a[k+1]进行匹配,即a[2],由于匹配成功,则next[5] = k = 2;
next[6]呢?正如前面所述,由于next[5]>0,故a[5]已经与T匹配了k个,则a[6]需要和a[k+1]进行匹配,即a[3],由于匹配成功,则next[6] = k = 3;
伪代码如下:
next[1] = 0;//前缀数组
k = 0;//代表匹配的个数
for i=2:length
while k>0 && a[k+1] != a[i]
k = next[k];
if a[k+1] == a[i]
k = k + 1;
next[i] = k;
return next
2、KMP实现
m = T.length
n = P.length
next = 前缀函数返回值
k = 0;//匹配的个数
for i = 1: m // 每个元素进行匹配
while k > 0 && P[k + 1] != T[i]
k = next[k];
if P[k+1] == T[i]
k = k +1;
if k == m
return i-n
k = next[k]//将k移动至next[k]
end
本站声明:网站内容来源于网络,如有侵权,请联系我们https://www.qiquanji.com,我们将及时处理。
微信扫码关注
更新实时通知
网友评论