1个公式就弄懂了KMP模式匹配算法，困扰我多年的问题终于解决了

欢迎大家来到IT世界,在知识的湖畔探索吧!

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

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

朴素模式串匹配算法

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

欢迎大家来到IT世界,在知识的湖畔探索吧!

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

在匹配到第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]; } }

欢迎大家来到IT世界,在知识的湖畔探索吧!

由此可以写出KMP算法：

欢迎大家来到IT世界,在知识的湖畔探索吧!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匹配的算法代码如下：

欢迎大家来到IT世界,在知识的湖畔探索吧!/ * 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研究僧大师兄