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、科技、技术方面的知识、经验，如果你喜欢的话，可以加个关注收藏一下吧！
,
