最新消息:点击查看大S的省钱秘笈

字符串匹配算法:KMP学习心得

编程相关 Slyar 348浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。

这周的数据结构课讲的是串,本以为老师会讲解KMP算法的,谁知到他直接略过了...没办法只能自己研究,这一琢磨就是3天,期间我都有点怀疑自己的智商...不过还好昨天半夜终于想明白了个中缘由,总结一些我认为有助于理解的关键点好了...

书上有的东西我就不说了,那些东西网上一搜一大片,我主要说一下我理解的由前缀函数生成的next数组的含义,先贴出求next数组的方法。

当一个字符串以0为起始下标时,next[i]可以描述为"不为自身的最大首尾重复子串长度"。

也就是说,从模式串T[0...i-1]的第一个字符开始截取一段长度为m(m < i-1)子串,再截取模式串T[0...i-1]的最后m个字符作为子串,如果这两个子串相等,则该串就是一个首尾重复子串。我们的目的就是要找出这个最大的m值。

例如:

KMP算法

若 i = 4 ,则 i - 1 = 3 , m = next[4] = 2

从T[0...3]截取长度为2的子串,为"ab"

从T[0..3]截取最后2个字符,为"ab"

此时2个子串相等,则说明 next[4] = 2 成立,也可证明 m = 2 为最大的m值。

本来一开始我是没有加"不为自身"这个限制条件的,可是后来我发现一种情况:

KMP算法

若 i = 4 ,则 i - 1 = 3 , m = next[4] = 3

从T[0...3]截取长度为3的子串,为"aaa"

从T[0..3]截取最后3个字符,为"aaa"

此时2个子串相等,则说明 next[4] = 3 成立。

但是我发现如果next[4] = 4:

从T[0...3]截取长度为4的子串,为"aaaa"

从T[0..3]截取最后4个字符,为"aaaa"

此时2个子串也是相等的,那么是不是说明 next[4] 应该等于4呢?

仔细观察后发现,如果 next[4] = 4 ,那么T[0...3]的前4个字符和后4个字符是重合的,并且重复子串和T[0...3]也是相等的。看过教材后发现教材中给出的前缀函数定义有一句为:next[j] = max{k | 0 < k < j 且 'p[0]...p[k-1]' = 'p[j-k+1]...p[j-1]'},应该不包含子串为本身的情况...

这样再做PKU 2406 和 PKU 1961 的时候就很简单了,用 length - next[length] 求出"不为自身的最大首尾重复子串长度",此时需要多求一位next[length]值,若最大重复子串的长度是length的非1整数倍,则证明字符串具有周期重复性质。

PKU 2752 是求 前缀 == 后缀 的长度,也就是首尾重复子串长度,利用next数组记录的"不为自身的最大首尾重复子串长度"可以马上得到结果。

恩,先说这么多吧,可能有不对的地方,以后理解的更深了再回来改...哪位大牛路过看到错误请指出哈。

转载请注明:Slyar Home » 字符串匹配算法:KMP学习心得

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (19)

  1. 赞“不为自身的最大首尾重复子串长度”~怎么在百度搜算法总能搜到南哥的博客里来~~
    小佳_Jessica2年前 (2015-01-12)回复
  2. 楼主这种算法求出来的next应该是错的 比如aaab这个串,next =2
    Derek3年前 (2013-09-10)回复
    • -1 0 1 2 No error.
      Slyar3年前 (2013-09-10)回复
      • 那跟算法导论上面的不一样吧,按照那上面应该是-1,0,1,-1 不知道有啥区别,只看过算法导论的实现。 请教~
        Derek3年前 (2013-09-11)回复
  3. 可不可以转载到我博客哦~~~(*^__^*)
    cherryfang5年前 (2012-05-24)回复
  4. 今天重看kmp(严xx那本书),头那个大啊
    荒野无灯5年前 (2011-10-25)回复
  5. 同样遭遇“直接略过了”的路过
    荒野无灯5年前 (2011-10-25)回复
  6. @FLex 没事,每个人都有不同的见解,我也只是在个人博客上发点心得哈~~今天怎么这么多人看这篇文章的...
    Slyar5年前 (2011-08-28)回复
  7. .....刚才就一时激动,因为我研究这个挺久的,对这个有着不同的见解,对不起了LZ..真的对不起了......
    FLex5年前 (2011-08-28)回复
  8. Thank You楼主,让我有点新的心得
    CMD5年前 (2011-08-28)回复
  9. lz切中要害,讲解的很清晰,谢谢啦!
    匿名5年前 (2011-07-22)回复
  10. @wOOL, 囧...输英文还得切换...我懒...明天去ACM珠海赛当炮灰...
    Slyar8年前 (2009-04-25)回复
  11. @Slyar 我想说我不会C/C++,勉勉强强能看懂的程度 PS: 别把Python翻译成中文好吧 囧
    wOOL8年前 (2009-04-25)回复
  12. @wOOL, 没事,我拿Google Reader翻墙...我有等宽字体...好长...你至于把每一步都写得那么清楚么...还用蟒蛇写代码...不过很清晰...
    Slyar8年前 (2009-04-25)回复
  13. @Slyar 恩,被墙奸了 https://docs.google.com/Doc?id=dm48v73_569cr9fcscd&hl=en 字体需要是ucida Console才能看到对称。。。 我深度怀疑我昨天没睡到12点结果脑残了才会写一篇如此废话的文章
    wOOL8年前 (2009-04-25)回复
  14. @wOOL, 阿宅...难道你的博客必须翻墙才能看么...
    Slyar8年前 (2009-04-25)回复
  15. 你说你诱惑我研究这个干虾米 https://iwool.wordpress.com/2009/04/25/kmp/ 我写出来自己都不想看第二遍
    wOOL8年前 (2009-04-25)回复
  16. 学习学习!~改明也当老师去!~
    v堡8年前 (2009-04-22)回复