KMP详细解释及KMP算法模板

KMP是什么，KMP解决什么类型的问题

KMP全称为Knuth Morris Pratt算法，是一种高效的字符串匹配算法，寻找一个字符串中是否包含另一个字符串，例如

char *s = "ababababcab"; char *p = "ababc";

s为模板串(主串)，p为子串，在s中找到p的位置

暴力匹配算法 O(n*m)

暴力匹配算法不做过多解释，举个例子即可 匹配到第4个字符时匹配失败则i+1继续向后匹配

ababababcab ababc

则i+1继续向后匹配

ababababcab     ababc

匹配失败继续向后匹配直到如图

ababababcab         ababc

匹配成功 此时我们可以发现当我们已经匹配了一部分字符串但下一个字符不相等时，我们还有一些信息可以利用，比如

ababababcab     ababc

这时已经匹配了4个字符相等，我们可以根据这个信息来简化算法时间复杂度，这时我们引入KMP算法

KMP算法O(n+m)

我们可以利用已经匹配的字符来简化枚举过程，当已经匹配成功了4个字符时，我们是不是可以让字串向后移动来使得子串和模板串继续匹配？ 例如

ababababcab     ababc

此时我们让子串向后移动而模板串不动，使得模板串可以继续向后继续匹配

ababababcab         ababc

此时匹配成功则继续向后匹配 而这样的移动就是KMP的next数组的用处 next数组的含义是一个固定字符串的最长前缀和最长后缀相同的长度，并且长度小于(不能等于)固定字符串本身，使得当匹配失败我们让子串向后移动最少的距离使模板串可以继续匹配，也就是说在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，子串应该跳到哪个位置 例如

假设我们在模板串的i位置和字串的j+1的位置匹配失败，此时我们将字串向后移动 j是我们匹配成功的最后一个字符 我们令j = next[j], 回忆一下next的数组含义next数组的含义是一个固定字符串的最长前缀和最长后缀相同的长度，此时

字符串移动到P2的状态，而这时P1，P2的绿色部分相等才能和模式串继续匹配，我们还可以发现

此时P1，P2的这两个绿色部分也是相等的，所以P中的绿色部分是相同的

所以也说明了next数组含义是一个固定字符串的最长前缀和最长后缀相同的长度，让前后缀相同我们才能使模板串继续匹配，而最长则保证了我们能找到所有的与模板串匹配的子串同时也能使子串与模板串尽快匹配，我们先不管next数组是怎么求得的我们先利用next数组实现KMP算法

KMP算法流程

// s[]是模板串，p[]是子串，n是s的长度，m是p的长度 // 匹配 for (int i = 1, j = 0; i <= n; i ++ )//由于我们令i与j+1匹配，所以i初始化为1, j初始化为0, 同时s与p的第一个字符在1位置，不在0位置 { while (j && s[i] != p[j + 1]) j = ne[j];//当j不为0且子串不能和模板串继续匹配时，让j = next[j], 判断能否继续匹配 if (s[i] == p[j + 1]) j ++ ;//如果能继续匹配，则继续 if (j == m) { j = ne[j]; // 匹配成功后的逻辑 } }

next数组实现

再强调一遍next数组含义next数组的含义是一个固定字符串的最长前缀和最长后缀相同的长度，由于next数组只与子串有关所以我们应该先对子串进行预处理，处理出next数组，处理next数组方式也与KMP实现过程类似。我们把P子串当作模板串和子串进行匹配，假设我们当前要求next[i]的值，匹配到如下情况 当p[i] == p[j+1]时，则j+1的值是不是就是next[i]的值，也就是长度为i的子串最长前缀和最长后缀相同的长度，如图 如果p[i] != p[j+1]，同KMP过程，1~j这一段是匹配的，则令j = next[j]，继续找下一个能匹配的位置，由于我们的j是从P串的开头位置开始，所以只要当p[i] == p[j+1]时，next[i] = j + 1. 上代码

//求模式串的Next数组： for (int i = 2, j = 0; i <= m; i ++ )//next[1] = 0, 所以i从2开始 { while (j && p[i] != p[j + 1]) j = ne[j];//匹配失败，j = next[j], 继续匹配 if (p[i] == p[j + 1]) j ++ ;//匹配成功，换个写法就是j = j + 1，就是让j到j+1的位置，并且赋值给i //如果p[i] != p[j + 1]，则出while循环的条件是j = 0, 说明没有前缀和后缀相同的长度，next[i]值也为0 ne[i] = j; }

KMP完整模板

// s[]是模板串，p[]是子串，n是s的长度，m是p的长度 //求模式串的Next数组： for (int i = 2, j = 0; i <= m; i ++ ) { while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j ++ ; ne[i] = j; } // 匹配 for (int i = 1, j = 0; i <= n; i ++ ) { while (j && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j ++ ; if (j == m) { j = ne[j]; // 匹配成功后的逻辑 } }

模板来自ACwing：ACwing模板