六之续、由KMP算法谈到BM算法

说明：初稿由滨湖提供，July负责KMP部分的勘误，yansha负责BM部分的修改。全文由July统稿修订完成。

    在此之前，说明下写作本文的目的：1、之前承诺过，这篇文章之后，KMP算法会写一个续集；2、写这个kMP算法的文章很多很多，但真正能把它写明白的少之又少；3、这个KMP算法曾经困扰过我很长一段时间。我也必须让读者真真正正彻彻底底的理解它。希望，我能做到。

    ok，子串的定位操作通常称做串的模式匹配,是各种串处理系统中最重要的操作之一.在很多应用中都会涉及子串的定位问题,如普通的字符串查找问题.如果我们把模式匹配的串看成一字节流的话,那应用空间一下子就广阔了很多,如HTTP协议里就是字节流,有各种关键的字节流字段,对HTTP数据进行解释就需要用到模式匹配算法.

   本文是试图清楚的讲解模式匹配算法里两个最为重要的算法：KMP与BM算法，这两个算法都较为高效，特别是BM算法在工程用应用得非常多的，然而网上很多BM算法都不算准确的。本文开始讲解简单回溯字符串匹配算法，后面过渡到KMP算法，最后再过渡到BM算法，希望能够讲得明白易懂。

    模式匹配问题抽象为：给定主串S(Source，长度为n)，模式串P(Pattern, 长度为m)，要求查找出P在S中出现的位置，一般即为第一次出现的位置，如果S中没有P子串，返回相应的结果。如下图0查找成功，则查找结果返回2：

    本文，接下来，将一步一步讲解KMP算法。希望看完本文后，读者日后对Kmp算法能做到胸中丘壑自成。文章有任何错误，烦请一定指出来。谢谢。

• 1、回溯法字符串匹配算法

    回溯法字符串匹配算法就是用一个循环来找出所有有效位移，该循环对n-m+1个可能的位移中的每一个index值，检查条件为P[0…m-1]= S[index…index+m-1]（因为模式串的长度是m，索引范围为0…m-1）。

该算法思维比较简单（但也常被一些公司做为面试题），很容易分析出本算法的时间复杂度为O(pattern_length*target_length)，我们主要是把时间浪费在什么地方呢，相信，你已经看到上面的代码注释中有这么一句话：“指针回溯，重新开始匹配”，这句话的意思就是好比我们乘坐一辆火车已经离站好远了，后来火车司机突然对全部乘客说，你们搭错了列车，要换一辆火车。也就是说在咱们的字符串匹配中，本来已经比较到前面的字符去了，现在又要回到原来的某一个位置重新开始一个个的比较。这就是问题的症结所在。

在继续分析之前，咱们来思考这样一个问题：为什么快排或者堆排序比直接的选择排序快？直接的选择排序，每次都是重复的比较数值的大小，每扫描一次，只得出一个最大（小值），再没有其它的结果信息能给下一次扫描带来便捷。我们看看快排，每扫一次，将数据按某一值分成了两边，至少有右边的数据都大于左边的数据，所以在比较的时候，下一次就不用比较了。再看看堆排序，建堆的过程也是O(n)的比较，但比较的结果得到了最大（小）堆这种三角关系，之后的比较就不用再每一个都需要比较了。
    由上述思考，咱们总结出了一点优化的归律：采用一种简单的数据结构或者方式，将每次重复性的工作得到的信息记录得尽量多，方便下一次做同样的工作，这样将带来一定的优化（个人性总结）。

     可以看出当匹配到g与h的时候，不匹配了（后面，你将看到，KMP算法会直接从匹配失效的位置，即g位置处重新开始匹配，这就是KMP的高效之处），模式串的下一个位置该怎么移动，需要回溯到第二个位置如：

在第二个位置发现还是不匹配，便再次回溯到第三个位置：

    其实可以分析一下模式串里，每个字符都不相同，如果前面有匹配成功，那移动一位或者几位后，是不可能匹配成功的。
 启示：模式串里有蕴含信息的，可以简化扫描。接下来深入的讨论另一算法KMP算法。

    如果是普通的匹配算法，那么接下来，模式串的下一个匹配将如上一节读者所看到的那样，回溯到第二个位置b处。而KMP算法会怎么做呢?KMP算法会直接把模式串移到匹配失效的位置上，如下图2-2，g处：

0<=i<n)失败的时候，接下来应该用什么位置的字符P[j_next]（我们设j_next即匹配失效后下一个匹配的位置）与主串S[i]开始匹配呢?重头开始匹配?No，在P[j]!=S[i]之前的时候，有S[i-j…i-1]与P[0…j-1]是相同的，所以S不用回溯，因为S[i]前面的值都已经确切的知道了。

    咱们先写下算法，你将看到，其实KMP算法的代码非常简洁，只有20来行而已。如下描述为：

• 3、如何求next数组各值

  所以，根据上面两个步骤，推出下一匹配位置j_next:

    下面，我们用变量k来代表求得的j_next的最大值，即k表示这S[i]、P[j]不匹配时P中下一个用来匹配的位置，使得P[0…k-1] = P[j-k…j-1]，而我们要尽量找到这个k的最大值。如你所见，当匹配到S[i] !=

    也就是说，如上图3-3，在第一次匹配中，就是因为S[2]=P[0]，所以在下一次匹配中，只需要比较S[3]=P[1]，跳过了几步?一步。那么k等于多少?k=1。即把 P 右移两个位置后，P[0]与S[2]不必再比较，因为前一步已经得出他们相等。所以，此时，只需要比较 P[1]与S[3]了。

    稍后，你将看到，由这个方法得出的next值还不是最优的，也就是说是不能允许P[j]=P[next[j]]出现的。ok，请跟着我们一步一步登上山顶，不要试图一步登天，那是不可能的。由以上，可得如下代码：

    上述求next数组各值的方法（代码）是否正确呢?我们来举一个例子，应用上述的get_next函数来试验一下，即具体求解一下next数组各元素的值（通过下面的验证，我们将看到上面的求next数组的方法是有问题的，而后我们会在下文的第4小节具体修正上述求next数组的方法）。ok，请看：

    所以，根据上面的代码，咱们首先要初始化nextval[0] = -1，我们得到第一个next数组元素值即-1（注意，咱们现在的目标是要求nextval[i]各个元素的值，i是数组的下标，为0.1.2.3）；

1（由下文的第4小节，你将看到，求出的next数组之所以有误，问题就是出在这里。正确的解决办法是，如下文的第4小节所述，++i，++j之后，还得判断patn[i]与patn[j]是否相等，即杜绝出现P[j]=P[next[j]]这样的情况）；

    第三步：接下来模式串指针指向下一位置next[1]=0处（注意此过程中主串指针是不动的），即模式串指针指向p[0]，即用p[0]与s[3]匹配（看起来，好像是k步步减小，这就是咱们开头所讲到的怎么求最大的数k使得P[0…k-1] = [j-k…j-1]）。而p[0]与s[3]还是不匹配。

1. nextval[0]=-1，满足循环if部分条件j==-1，所以，++i，++j，主串指针下移一个位置，从P[0]与S[4]处开始匹配，最后j==plen，跳出循环，输出结果i-plen=4，算法结束。

    不知，读者是否已看出，上面的匹配过程隐藏着一个不容忽略的问题，即有一个完全可以改进的地方。对的，问题就出现在上述过程的第二步。
    观察上面的匹配过程，看匹配的第二步，在第一步的时候已有P[3]=b与S[3]=c不匹配，而下一步如果还是要让P[next[3]]=P[1]=b与s[3]=c匹配的话，那么结果很明显，还是肯定会匹配失败的。由此可以看出我们的next值还不是最优的，也就是说是不能允许P[j]=P[next[j]]出现的，即上面的求next值的算法需要修正。
好比上面的例子。请容许我再次引用上面例子中的两张图。在上面的第一步匹配中，我们已经得出P[3]=b是不等于S[3]=c的。而在上面的第二步匹配中，根据求得的nextval[i]数组值中的nextval[3]=1，即让P[1]重新与S[3]再次匹配。这不是明摆着有问题么?因为P[1]也等于b阿，而在第一步匹配中，我们已经事先得知b是不可能等于S[3]的。所以，第二步匹配之前就已注定是失败的。

    这里读者理解可能有困难的是因为文中，时而next，时而nextval，把他们的思维搞混乱了。其实next用于表达数组索引，而nextval专用于表达next数组索引下的具体各值，区别细微。至于文中说不允许P=P[next[j] ]出现，是因为已经有P=b与S匹配败，而P[next]=P=b，若再拿P[1]去与S匹配则必败。

• 4、求解next数组各值的方法修正

    那么，上面求解next数组各值的问题到底出现在哪儿呢？我们怎么才能摆脱掉这种情况呢?：即不能让P[j]=P[next[j]]成立成立。不能再出现上面那样的情况啊！即不能有这种情况出现：P[3]=b，而竟也有P[next[3]]=P[1]=b。

    如果你还是没有弄懂上述过程是怎么一回事，请现在拿出一张纸和一支笔出来，一步一步的画下上述过程。相信我，把图画出来了之后，你一定能明白它的。
    然后，我留一个问题给读者，为什么上述的next数组要那么求?有什么原理么?

• 5、利用求得的next数组各值运用Kmp算法

    Ok，next数组各值已经求得，万事俱备，东风也不欠了。接下来，咱们就要应用求得的next值，应用KMP算法来匹配字符串了。还记得KMP算法是怎么一回事吗?容我再次引用下之前的KMP算法的代码，如下：

第三步：与上文中第3小节末的情况一致。由于上述第三步中，P[0]与S[3]还是不匹配。此时i=3,j=nextval[0]=-1,由于满足条件j==-1，所以进入循环的if部分,++i=4,++j=0,即主串指针下移一个位置，从P[0]与S[4]处开始匹配。最后j==plen，跳出循环，输出结果i-plen=4(即字串第一次出现的位置），匹配成功，算法结束。

1. 开始匹配，直到P[3]！=S[3]，匹配失败；
2. nextval[0]=-1，满足循环if部分条件j==-1，所以，++i，++j，主串指针下移一个位置，从P[0]与S[4]处开始匹配，最后j==plen，跳出循环，输出结果i-plen=4，算法结束。

    与上文中第3小节的四步匹配相比，本节运用修正过后的next数组，去掉了第3小节的第2个多余步骤的nextval[3]=1，所以P[1]继续与S[3]匹配，匹配失败（缘由何在?因为与第3小节的next数组相比，此时的next数组中nextval[3]已等于0）。所以，才只需要三个匹配步骤了。

    ok，KMP算法已宣告完结，希望已经了却了心中的一块结石。毕竟，这个KMP算法此前也困扰了我很长一段时间。耐心点，慢慢来，总会搞懂的。闲不多说，接下来，咱们开始介绍BM算法。