kmp算法的总结

时间:5年前   阅读:4445

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,我们将及时处理。

微信扫码关注

更新实时通知

上一篇:个人可以开通沪深300期权账户吗?

下一篇:安装好zblog打不开首页的解决方法

网友评论

请先 登录 再评论,若不是会员请先 注册