KMP算法的理解 – lijihong0723

  这么有名的串模式匹配算法,在此不作详细介绍了。如果有不了解的请看参考文献的两篇文章。

  这里,我只准备介绍一下该算法核心next数组的含义(怎么求,相关博客也很详细)。很多文章介绍next数组的时候,一上来会介绍字符串前缀和后缀的概念,我这里也提一下。给定一个字符串T[0…n],其前缀有:T[0], T[0,1], …, T[0…n-1],其后缀有:T[1], T[1,2], …, T[1…n]。

  既然是串匹配,则必然会有目标串和模式串,当然目标串的长度要比模式串大。这些基础知识在此不再赘述。

  传统暴力匹配算法(所有介绍KMP算法都会介绍,我在此不做阐述),一旦模式串和目标串发生失配时,模式串将回退至起始位置,目标串将回退至该轮比较起始位置的下一个位置(有点绕哈)。KMP算法解决的问题是,失配发生时,确保目标串不发生回退,仅改变模式串的位置(有的文章也称为滑动模式串)。

  设:目标串为S[0]S[1]…S[m],模式串为T[0]T[1]…T[n],m>n,现在处于如下匹配状态:

                 ↓

  目标串:s[0]…s[i-j]…s[i-1]s[i]…s[m]

  模式串:    T[0]…T[j-1]T[j]…T[n]

                ↑

  即:目标串S[i]和模式串T[j]发生了失配,现在怎么才能保持上面那个箭头,也就是i不变呢?换句话说,S[i]下一次该与T[?]比较呢?我们做如下分析:

  要想模式串向前滑动一个位置,也就是S[i]与T[j-1]比较,我们要保证什么?我们必须要确保:

        T[0]T[1]…T[j-2] == T[1]T[2]…T[j-1]      (1),

  若(1)做不到,则必然会导致S[i]与T[j-1]之前就发生失配了。为什么?因为根据之前匹配,我们有:

        S[i-j]==T[0], S[i-j+1]==T[1], … ,S[i-1]==T[j-1]  (2)

  模式串向前滑动一步,我们必须要保证:S[i-j+1]==T[0], S[i-j+2]==T[1], … ,S[i-1]==T[j-2],才能将匹配进行到S[i]与T[j-1],综合上述,我们必须确保(1)式成立,否则滑动没意义;

  同样的,要模式串向前滑动两部,类似的,我们必须保证:T[0]T[1]…T[j-3] == T[2]T[3]…T[j-1]。——上述分析的这些,不都是T[0]T[1]…T[j]前缀和后缀吗?!

  因此,根据上面分析,我们不难得出下述结论:要确保目标串中指针不变,那么下一个匹配的位置就是最大公共前缀的下一个元素。因为大多数语言数组索引以0开始,所以下一个位置就是最大公共前缀的长度了,对不对?于是,我们得到:

  失配发生时,有:下一个匹配位置 = k, T[0]T[1]…T[k-1] == T[j-k]T[j-k+1]…T[j-1] ,这个值定义为next[j],即

                next[j]=k  (3)

  那next[0]是什么呢?它没有前缀啊,这里我们将其定义为next[0]=-1,为什么这么定义,我想可能是特殊处理吧!如果没有公共前后缀,此时next[j] = 0,这也是符合(3)式定义的。

  另外还有一种情况我们没有讨论,就是参考文献[2]的优化部分:(3)式的得出没有考虑T[k] != T[j]这种情况,如果出现这一情况,则可以进一步优化,有next[j] = next[k],这样就进一步减少了比较。

  综合上述,我们有next数组表达式如下:

  next[j] = { -1, j == 0;

       { k, T[0]T[1]…T[k-1] == T[j-k]T[j-k+1]…T[j-1], T[k] == T[j]

        {   next[k],  T[0]T[1]…T[k-1] == T[j-k]T[j-k+1]…T[j-1], T[k] != T[j]

       { 0,  others.

  关于next数组解释至此为止,上述为个人学习总结,如有问题,请留言。时间紧张,故写的比较简单。

 

附:参考文献:

[1]从头到尾彻底理解KMP:http://blog.csdn.net/tukangzheng/article/details/38438481

[2]KMP串匹配算法解析与优化:http://www.cnblogs.com/tr0217/p/4735279.html

  

本文链接:KMP算法的理解,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量