KMP 深入理解next数组

一、引言

• KMP又称模式匹配算法，能够在线性时间内判定字符串A[1~N]是是否为B[1 ~ M]的子串，并求出A在B中各次出现的位置。

二、基本含义

• next数组：next[i] 代表A中以i结尾的非前缀子串（非前缀子串的意思就是不能和A完全相等的后缀子串） 与 A的前缀能够匹配的最大长度。
• 当不存在这样的前缀串时，显然next[i] = 0， 故next[1] = 0 （因为第一个字符前面没有字符串且第一个字符不是非前缀子串）
• 我们可以让A对B进行匹配，求出一个数组p。p[i]代表以i结尾的子串 与 A的前缀能够匹配的最大长度。 当p[i] = n（A的长度）代表匹配此位置成功。

三、next数组的求解

1. 朴素的求解next数组

• 假定A串为 abababbc
  

2. 优化求解next数组过程

void getNext() { //n串A串的长度
 for (int i = 2, j = 0; i <= n; i++) { //求解next[i] 
 	while (j && A[i] != A[j + 1]) j = ne[j]; //这时候找到一个符合的位置 A[i] == A[j + 1] 那么就停止了。
 	if (A[i] == A[j + 1]) j++; //这时候有2种情况，j==0:代表前面的串都不满足。 否则那么next[i] = j + 1。
 	ne[i] = j; // 求解出ne[i] 。  
 }
}

三、kmp算法

• 这时候我们与串B匹配的过程和求解next的过程大同小异。

void kmp() {
	for (int i = 1, j = 0; i <= m; i++) {
		while (j && B[i] != A[j + 1]) j = ne[j]; 
		if (B[i] == A[j + 1]) j++; //在前面已经匹配的长度的基础上加1
		p[i] = j; //代表B串以i结尾的子串与 A的前缀的最大匹配长度 匹配串为B[i - j + 1, i]
		//if (j == n) {//匹配成功 }
	}
}

四、其他应用

• 最小循环节