文章来源：c_cloud KMP

思想

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（The Knuth-Morris-Pratt Algorithm，简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息

首先介绍几个算法的术语：

前缀

前缀指除了最后一个字符以外，一个字符串的全部头部组合

后缀

后缀指除了第一个字符以外，一个字符串的全部尾部组合

部分匹配值

部分匹配值就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例

“A”的前缀和后缀都为空集，共有元素的长度为0；
“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；
“ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；
“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；
“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

在KMP算法中，模式字符串向右移动的位数 = 已匹配的字符数 - 对应的部分匹配值

部分匹配的实现

下面给出模式串右移位数：

void makeNext(const char P[],int next[])
{
    int q,k;//q:模式字符串下标；k:最大前后缀长度
    int m = strlen(P);//模式字符串长度
    next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
    for (q = 1,k = 0; q < m; q++)//for循环，从第二个字符开始，依次计算每一个字符对应的next值
    {
        while(k > 0 && P[q] != P[k])//递归的求出P[0]到P[q]最大的相同的前后缀长度k
            k = next[k-1];
        if (P[q] == P[k])//如果相等，那么最大相同前后缀长度加1
        {
            k++;
        }
        next[q] = k;
    }
}

已知前一步计算时最大相同的前后缀长度为k（k>0），即P[0]···P[k-1]；　　

上面的代码中

while(k > 0 && P[q] != P[k])//递归的求出P[0]到P[q]最大的相同的前后缀长度k
            k = next[k-1];
        if (P[q] == P[k])//如果相等，那么最大相同前后缀长度加1
        {
            k++;
        }

这几步是比较难理解的，实际上这几步就是上面我们手工对字符串”ABCDABD”进行的部分匹配值计算。

“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；
“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；
“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0

截取这几步，我们按照从左向右的顺序进行模式匹配，字符串”ABCDABD”依序增加的话，因为前缀与后缀相同的子字符串顺序是一致的，所以部分匹配值增加的话也是根据上一字符串的部分匹配值基础进行。

我们拿到一个字符串计算部分匹配值，如果上一字符串匹配值为0，我们肯定会先将字符串的第一位与最后一位进行匹配，因为此时字符串最多只能可能有1的部分匹配值，否则的话上一字符串匹配值不会是0。

如果上一字符串部分匹配值为k时，我们将字符串的前（k+1）位与后（k+1）位进行匹配，如果匹配成功，则next值为k+1，

如果匹配失败的话：

1 2	while(k > 0 && P[q] != P[k]) k = next[k-1];

P[k]已经和P[q]失配了，而且P[q-k] ··· P[q-1]又与P[0] ···P[k-1]相同。假设模式串长度length，失配也就是讲模式串的前k位与P[length-k-1:length-2]相同，而P[k]与P[length-1]不同。看来P[0]···P[k-1]这么长的子串是用不了了，那么我要找个同样也是P[0]打头、P[k-1]结尾的子串，即P[0]···Pj-1，看看它的下一项P[j]是否能和P[q]匹配。循环进行，直到k=0，从头再开始。

那么为什么j==next[k-1]呢？上一次k的匹配失败，导致求下一个k值只能在模式串的前next[k-1]字符中寻找，而非next[k]-1。因为前面的寻找依然是一次模式匹配，所以next数组的求值实际上就是一个递归。

“ABCABHABCAB” 部分匹配值为5
“ABCABHABCABC”

继续增加字符时出现失配，j=next[k-1]，也就是求next[4]=2。因为之前的”ABCABH”没法使用了，但是”ABCAB”是匹配过的，”H”无法使用，就在”ABCAB”中寻找匹配度，目的是尝试对下标next[4]与整个模式串的最后一位匹配。