KMP算法可以说是一个很经典的模式匹配算法了，它一种改进的字符串匹配算法，但很多人就是不理解，甚至多看几次之后也没有理解透彻。

我们要查找S字符串串中是否包含P字符串，将P串称之为模式匹配串(以下简称模式串)。

朴素模式串匹配算法

我们先用一个动图来看不用KMP匹配的 朴素模式串匹配算法：

浅显易懂吧！但是呢，朴素的模式串匹配算法是有效率问题的！比如像下面这种：

在匹配到第5个字符时，发生了P串和S串不匹配的情形，然后按照朴素的算法，需要回溯 i 指针到 1 位置，回溯 j 指针到 0 位置，然后我们依次移动P串进行匹配计算：

在i = 3时，此时后面就有S[3] = P[0], S[4] = P[1], S[5] = P[2]：

然后S[6] != P[3]:

才发现又是不匹配的，其中我们可以用肉眼观察到，当S[1]和P[0]发生不匹配时，P串依次的从S串第1个位置，第2个位置进行比较，只有到S串第3个位置字符是A时才和P串的第0个字符匹配，而且后面的两个字符也能够匹配，但是，S串第5个字符是不匹配的。

假如我们是通过肉眼判断的话，当

这时不匹配时，我们应该直接移动 j 到

进行匹配判断，因此，朴素的模式匹配是有一部分匹配判断是多余的，我们要想办法把它优化，在S[5] != P[5] 时，直接进行判断 S[5] 是否等于 P[2]。这是因为P[0] == P[3], P[1] == P[4]；P串前后有相同的子串，可以看下图知道：

由于S[3] = P[3], S[4] = P[4]，而 P串前后有相同的子串：P[0] == P[3], P[1] == P[4]，因此，我们可以直接进行判断S[5] 是否 等于 P[2]。也就是说当S[i] 和 P[j] 不匹配时，我们可以决定 j 的下一个位置是什么，从而使 i 指针不产生回溯。

推广到一般情况，我们可以用数学来证明这个事情：

这就有了KMP算法，我们假设S串下标是i，P串下标是 j。当P串中存在重合的子串时，我们需要分析出j指针指向的下一个位置，为了记录所有 j 取值的情况，用next数组来记录每一个P串的字符不匹配时需要将 j 指针移动到的位置下标。

KMP算法核心

核心思想：模式串中有重合的子串，那么当模式串p[j]匹配失败时，要移动到下标为k的位置进行匹配，k需要满足：0 ~ k 之间的 k+1 个字符与 j-1-k ~ j-1 之间的 k+1 个字符相同。next数组用于存放匹配失败时，next[j]代表需要进行匹配下一个字符的位置p[next[j]]。

可以用数学语言表述为：

模式串p中有n个字符，其中

如果存在

使得

那么令

否则(p中没有字符相同)，令

说明：

• 当 k = 0 时，表示模式串p中前后只有一个字符能够重合，此时要从p[0](从头开始)匹配；
• 当 k = -1 时，表示模式串中没有可以前后重合的部分子串，此时需要将原始串的指针下标(i)后移。

记住：k = next[j]; 当 s[i] != p[j]时，需要将j指针移动到p串的k下标位置，那么next[j]就用来存储这个k。

具体解释：

• 第一种情况：j == 0时，s[i]和p[j]不匹配，那j指针不可能再向左移动了，此时应该要i指针向后移动。这种情况，记next[j] = -1;

• 第二种情况：j == 1时， s[i]和p[j]不匹配，那j指针显然是要移动到0位置的。这种情况，记next[j] = 0;

• 第三种情况：p[j] = p[k] 时，有 next[j+1] = next[j] + 1;

证明：

因为p[j]之前有 p[j-k ~ j-1] = p[0 ~ k-1]; 所以 next[j] = k;

那此时有 p[j] = p[k]；可以得到 p[j-k ~ j-1] + p[j] == p[0 ~ k-1] + p[k];

即：p[j-k ~ j] == p[0 ~ k];

那么 next[j+1] = k + 1 = next[j] + 1;

• 第四种情况：p[j] != p[k] 时，此时应该是 k = next[k];

代码中为了保证循环依次计算j之前的重合子串，用j+1表示当前匹配不成功的字符位置，则计算next数组的算法如下：

void getNext(char *p, int next[]){    int j = 0, k = -1, len = strlen(p);    if (len == 0)    return;    next[0] = -1;    while (j < len-1)    {        if (k == -1 || p[j] == p[k])            next[++j] = ++k; //next[j+1]记录p[j+1]匹配失败时需要跳转的位置        else            k = next[k];    }}

由此可以写出KMP算法：

int KMP(char s[], char p[]){    int[] next = getNext(p);    int i = 0, j = 0;    while (s[i] && p[j])    {        if (j == -1 || s[i] == p[j])            i++, j++;        else        j = next[j]; // j回到指定位置    }    if (p[j])        return -1;    return i - j;}

改进的KMP算法

回顾第三种情况：p[j] = p[k] 时，有 next[j+1] = next[j] + 1;

当s[i] != p[j]时，需要将 j 移动到 next[j]，然而由于 p[j] == p[next[j]]，导致移动j之后 s[i] 和 p[next[j]]仍然不匹配，此时需要继续将j移动到next[next[j]]进行比较；

显然，当p[j] 与 s[i]不匹配时，若p[j] == p[next[j]]，就可以跳过j移动到next[j]这一步，直接进行移动到下一步。

因此，修正后的nextval数组如下：

改进思想：

在保证

p[i] = p[j - k + i],(i = 0, 1, ..., k)

后，再继续检查 p[j] 是否与 p[k] 相等？(此时原本是令 next[j] = k)

因为此时 k 记录的是 p[j] 发生不匹配时，需要直接跳到下次比较的位置；

所以：

• 如果 p[k] = p[j] ，则同样发生不匹配，这时应该令 next[j] = next[k](因为 p[k] 与 p[j] 相同，则当前字符 p[j] 不匹配时，p[k]同样也不匹配，next[k]记录的是 p[k] 不匹配时需要跳转的位置，因此 p[j] 不匹配应该直接跳转到 next[k] 位置进行比较)；
• 如果 p[k] != p[j]，那么当 p[j] 不匹配时才应该跳转到 p[k] 再次进行匹配，此时应令 next[j] = k。

改进算法如下：

void getNextval(char p[], int nextval[]){    int j = 0, k = -1, len = strlen(p);    if (len == 0)        return;    nextval[j] = k;    while (j < len-1)    {        if (k == -1 || p[j] == p[k])        {            ++j, ++k;            if(p[j] != p[k])                nextval[j] = k;            else            nextval[j] = nextval[k];        }        else            k = nextval[k];    }}

kmp匹配的算法代码如下：

/*** kmp模式匹配子串* 参数：* *str - 源串* *substr - 目标串*/int kmp(char *str, char *substr){    int i=0, j=0, slen = strlen(str), plen = strlen(substr);    int *nextval = (int *) calloc(plen, sizeof(int));    getNextval(substr, nextval);    while(i < slen && j < plen)    {        if( j == -1 || str[i] == substr[j])            i++, j++;        else            j = nextval[j];    }    if(j == plen)        return i - j;    else        return 0;}

如果觉得这篇文章对你有帮助，就帮我点赞并转发吧！我会持续分享IT、科技、技术方面的知识、经验，如果你喜欢的话，可以加个关注收藏一下吧！@IT研究僧大师兄