KMP算法

KMP算法 kmp算法

先上代码

class Solution {
public:
	// kmp算法解决
	int strStr(string haystack, string needle) {
		// 求needle的next数组

		if (needle == "") {
			return 0;
		}
		int* next = new int[needle.size()];

		int j = 0, k = -1;
		next[0] = -1;
		while (j < needle.size() - 1) {
			if (k == -1 || needle[j] == needle[k]) {
				k++;
				j++;
				next[j] = k;
			}
			else { // 回溯，找当前k位置前的公共子串
				k = next[k];
			}
		}
	
		// kmp匹配
		int i = 0;
		j = 0;

		int n = haystack.size();
		int m = needle.size();
		while ( i < n && j < m) {
			if (j == -1 || haystack[i] == needle[j]) {
				i++;
				j++;
			}
			else {
				j = next[j]; // 回溯
			}
		}
		if (j >= needle.size()) {
			return i - needle.size();
		}
		else {
			return -1;
		}
		
	}
};

求next数组 next数组的本质：

子串中某个字符前的字符串的最长公共前后缀表示该处字符不匹配时应该回溯到的字符的下标

k = next[k]的意义

当子串的k处不匹配时，应将子串回溯到 next[k] 的位置；当子串的k处不匹配时，找k处前的最长公共前后缀；

// 建立next数组
		int* next = new int[s.size()];

		int j = 0;
		int k = -1;
		next[0] = -1;
		while (j < s.size() -1) {
			if (k == -1 || s[k] == s[j]) { // 如果成立就继续向前加
				k++;
				j++;
				next[j] = k;
			}
			else { // 回溯，此时s[k] == s[j]不成立
				k = next[k];
			}
		}

KMP算法

int i = 0;
		j = 0;

		int n = haystack.size(), m = s.size();
		
		while (i < n && j < m) {
			if (j == -1 || haystack[i] == s[j]) {
				j++;
				i++;
			}
			else {
				j = next[j];
			}
		}

		if (j >= s.size()) {
			return i - m;
		}
		else {
			return -1;
		}