KMP算法

求Next数组

Next数组用来计算匹配字符的回退位置，有多种求解的思路，本篇列举两种。不同的Next数组使用起来也会有所差异。

设置场景：

需要查找的字符串：a a b b c c f a a b b c f

模式字符串：a a b b c f

方式一

• 定义next[0] = -1; next[1] = 0。
• next[i] 表示下标从 0 到 i-1 的字符串，最大的相等前缀字符串和后缀字符串的长度
• 模式字符串对应的next数组为：[-1, 0, 1, 0, 2, 0]
• 若第i位字符不匹配，则回退到next[i].
• 求解：
  • 若next[i] == k，则说明s[i-1] 前有k个相等的字符，即前缀s[0]...s[k-1] == s[i-k]...s[i-1]
  • 若s[i] == s[k]，则next[i+1] = k + 1;
  • 若s[i] != s[k]，则比较s[i] 和 s[k] = s[ next[i] ]，若仍然不相等，则 s[ next[i] ]回退为s[ next[next[i] ] ] 直到 s[i] == s[k]，此时next[i+1] = k + 1 = next[next[i] ...] + 1; （k为最终next数组回退到的下标）

void GetNext(std::vector<int>& next, const std::string& s) {
	next[0] = -1;
	next[1] = 0;
	int size = s.size();
	if (size < 3) return;

	int k = 0;  //记录最长相等子串

	for (int i = 2; i < size; i++) {
		while (k > -1 && s[k] != s[i - 1]) {  //回退
			k = next[k];   
		}
		if (k == -1 || s[i - 1] == s[k]) {   // next[i] 代表前 i-1 长度的子串，所有s[i-1]
			next[i] = k + 1;	
			k++;
            
            /* 优化写法
			k++;
			if (s[k] == s[i]) {   //当前字符和回退的字符相等
				next[i] = next[k];
			}
			else {
				next[i] = k;
			}*/
		}
	}
}

• Next数组的优化

若回退到的字符和当前字符相同，当前nextval[i] = 回退位置的nextval[i] ；若不同，当前nextval[i] = 原来的next[i]。

方式二

• next[0] = 0;
• next[i] 表示下标从 0 到 i 的字符串，前缀字符串（不包含最后一个元素）和后缀字符串（不包含第一个元素）最大的相等长度。
• **注意：**字符串 i s s i p ，其next数组为[0, 0, 0, 1, 0]，“iss”和“ssi“对称但并不相等，只有'i'是相等的。
• 模式字符串对应的next数组为：[0, 1, 0, 2, 0, 0]
• 若第i位字符不匹配，则回退到next[i-1].

求解可参考方式一：

• 若next[i-1] == k，则说明s[i-1] （包含）前有k个相等的字符，即前缀s[0]...s[k-1] == s[i-k]...s[i-1]
• 若s[i] == s[k]，则next[i] = k + 1;
• 若s[i] != s[k]，则比较s[i] 和 s[k] = s[ next[i-1] ]，若仍然不相等，则 s[ next[i] ]回退为s[ next[next[i-1] ] ] 直到 s[i] == s[k]，此时next[i] = k + 1 = next[next[i-1] ...] + 1; （k为最终next数组回退到的下标）

void GetNext(std::vector<int>& next, const std::string& s) {
	next[0] = 0;
	int size = s.size();
	int k = 0;  //记录最长相等子串

	for (int i = 1; i < size; i++) {
		while (k > 0 && s[k] != s[i]) {
			k = next[k-1];   //遇见冲突看前一位
		}
		if (s[i] == s[k]) {   // next[i] 代表前 i-1 长度的子串，所有s[i-1]
			k++;
		}
		next[i] = k;
	}
}

• k和i还可以表示不同的含义：k为前缀末尾，也表示最大相等子串的长度。i为后缀末尾
• 如果s[i] != s[k]，则k向前回退，直到相等

KMP返回字符串下标

int KMPFind(const std::string& Original, const std::string& sub) {
	int OriginlLen = Original.size();
	int SubLen = sub.size();
	if (OriginlLen == 0 || SubLen == 0) return -1;

	std::vector<int> next(SubLen, 0);
	GetNext(next, sub);
	
	int j = 0;
	for (int i = 0; i < Original.size(); i++) {
		while (j > 0 && Original[i] != sub[j]) {
			j = next[j - 1];
		}
		if (Original[i] == sub[j]) {
			j++;
		}
		if (j == sub.size()) {
			return (i - sub.size() + 1);
		}
	}
	return -1;
}