关于串模式匹配算法，相信很多讲解数据结构的书籍都会有讲解，这里先大概提一下。

串模式匹配算法

所谓串模式匹配，就是在一个字符串中寻找/匹配另外一个字符串，一般返回第一个匹配的起始位置。对于这种匹配，最容易想到的匹配算法莫过于从原始字符串头开始依次匹配要寻找的字符串直到完全匹配，如果中间遇到不匹配的情况则原始字符串往左挪一个字符继续进行匹配，直到找到匹配或者匹配完了可能的起始位置。后来又有人很聪明的想到了改进的办法，也就是KMP算法，减少了很多不必要的回溯，提升了效率。不过在我接触KMP算法的时候困惑了一段时间(而且用的教材该算法的C语言实现有错误，也是醉了)于是记录一下，以后方便自己复习，或许还能够帮助到其他人学习。

基本匹配算法

基本匹配算法就是前面提到的最容易想到的那种。

例如有如下匹配：

模式匹配开始

刚开始从头开始匹配，然后发现第一个字符就匹配失败，于是继续向后找：

发现字符、继续向后

直到找到what中的t，但是接着匹配h又失败：

中间匹配失败、进行回溯

于是接着往后尝试，直到the的t匹配成功，于是接着匹配h与e，都匹配成功，于是返回结果5：

匹配成功

我这里用python实现了一下，可以作为参考：

#coding: utf-8
#Date: 2016.03
#Author: Quarkay blog: www.quarkay.com

testStr = 'this is the testStr'
pat = 'is'

tmp = i = j = 0
testMax = len(testStr) - 1
patMax = len(pat) - 1

while i<=(testMax-patMax) and j<=patMax :
    if testStr[i] == pat[j] :  #当前匹配的字符相等，于是都继续往后进行匹配
        i += 1
        j += 1
    else :
        tmp += 1  #发生了不匹配的情况，原始字符串往左挪一位继续尝试匹配
        i = tmp
        j = 0  #要搜索的字符串索引归零，重新开始往后进行匹配
print tmp

可见，匹配的过程中会有大量的回溯，比较浪费时间。那么有没有一种方法能够在匹配的过程中不那么需要回溯，只用一个劲的往左挪动原始字符串呢？答案是：有的。这就是KMP算法了。

KMP算法详解

以下阐述比较抽象不像书上有推倒公式和图，不过意思一样，大概看看就好。

对于KMP算法，可以先看看这个例子：在abcabb中匹配abb，在普通模式中，显然会先前两位匹配成功，即匹配到ab然后开始匹配c与b，匹配失败，那么是不是需要再像上面一样，从原始字符串的b开始匹配a这样呢？然而直觉上，abb本身就透露出来，它的第二个b匹配失败的时候，直接用a去尝试匹配刚刚与b匹配的值就好（因为a!=b），也就是说匹配串自身透露出来的一些特性可以用来辅助避免一些不必要的回溯。

例如对于匹配串ababc这种类型，如果和原始字符串匹配到c的时候匹配失败，那么可以想想着把匹配串右移两位然后用第三位a继续与c刚刚匹配的值进行匹配即可（因为前面的刚好可以ab“重合”）。显然，这样就通过利用匹配串本身的一些特性避免了对原始字符串不必要的回溯。那么剩下的就是分析这种特性具体是什么特性了。

还是用ababc来举例，到c的时候之所以知道可以用第三个字符a去继续尝试匹配是因为前面ab有重复，一共两位，所以匹配串往右边挪动两位之后ab依然是匹配的，所以可以直接用第三位a去匹配之前c匹配的那一位。综合起来说就是，匹配串从开头到匹配失败的前一位这一段里边，从头开始的m位和最后的m位相同，那么直接向右边挪动，让开始的m位和后边的m位重合，然后用第m+1位继续去和原始字符串进行匹配即可，当然了，这个m可能有多种可能的值，但是显然，取用最大的可以最大程度避免回溯。

那么接下来的工作就是寻找每一位所对应的串（正如我前面提到，准确的说法是这一位前面的串）头部和尾部最大重合字符数量了。首先当然是从头开始，第一位比较特殊，设置为0，很显然和原始字符串匹配的时候如果第一位就匹配失败直接挪动匹配下一位即可。然后从第二位开始了（可以在脑海中想象两个箭头）。毫不意外，因为第一位和第一位肯定是相等的，所以第二位对应的是1，然后第三位开始（它的前头是第一位和第二位），如果第二位和第一位相等，那么对应的就是2，然后第四位如果第三位又等于第二位，那么第三位对应的就是2+1=3，然后假设前面q位都已经算出来对应的位数了假设是k位，假设此时前面的箭头指向的和后面的终于出现了不等的现象，怎么办？这可是归纳的关键。

这么说可能不太直观，可以参考下图（注意index从0开始）：

P[K]位置匹配失败

假设此时，P[q-k] ~ P[q-1] 与 P[0] ~ P[K-1]相同,但是前面的箭头指向的p[q]与后面的箭头指向的p[k]不等了。怎么办？既然前面这么长的不能继续下去了，那也要尽可能找个第二长的继续尝试，想想数学归纳法，这里也是类似，要知道能倒p[q]这里前面的肯定都已经有对应的位数了，那么找到p[k-1]对应的位数，假设是j，那么就是如下图的情况：

直接往右边挪动匹配串即可

那么如果依然p[j]!=p[q]怎么办？显然，继续上一步即可。再找p[j]对应的位数，再......如果一直都找不到，那么就会有一步得到０（也就是说找到了ｐ[0]），如果是这种情况的话直接给此位对应位数置１即可，意思就是说和原始字符串匹配的时候如果这一位匹配失败的话，匹配串直接挪到最右边用第一位接着匹配即可，因为很显然透过匹配串自身的信息得到，这种情况下你怎么挪都没有能有“重合”的。

KMP算法中获取next数组的具体代码实现

next数组，也就是前面说的那个位数的对应关系，显然用数组存放再合适不过了。前面说的两个箭头，用两个变量来存储index即可表示，同时需要注意数组的下标是从0开始的，而为了方便描述低级位第几位这种说法都是从一开始的。我看的教材Po的代码问题也是出在这个地方。

Python版本示例：

#coding: utf-8
#Date: 2016.03
#Author: Quarkay blog: www.quarkay.com

pat =  'abaabcac'
'   ####01122312'

def get_nextArr(pat):
    'get the next array of pattern that will be used in kmp algorithm'
    pat = ' ' + pat  #注意这里，我是这么解决index问题的
    patLen = len(pat)-1
    nextArr = [None]*(patLen+1)

    i = 1
    j = 0
    nextArr[0] = patLen  #index0不浪费，存储匹配串长度好了
    nextArr[1] = 0   #第一位存储0，前面有说过

    while i < patLen :
        if j == 0 or pat[i] == pat[j] : #j==0 或在里头是因为前面说的到这步置为1的
            i += 1                      #最后总是正好可以归纳进去，想想数学归纳法
            j += 1
            nextArr[i] = j
        else :
            j = nextArr[j] #尽量去找个最长的可以用的有种递归的即视感(不过不是递归)
    return nextArr

print get_nextArr(pat)

写到这里想到了一个小小的优化，其实可以在上面的代码中在怼到第一位对应的0的时候，顺便判断一下第一位和前面的箭头指向的相不相等，如果不想等直接置0即可，一来可能减少匹配串后头寻找对应的位数的时间，二来外部调用next数组的时候少了一次不必要的比较。缺点是相比较教科书的“标准”代码而言会稍微复杂一点。

昨天写课程作业写到太晚了，今天好累...

还有PHP实现版本就不贴了，都放在GitHub：

KMP算法实现，Python和PHP示例代码

自我感觉是写东西又臭又长，不知道怎么表达，得多练练。