# kmp 讲解

代码随想录 (programmercarl.com)

当我们需要在一个字符串中查找另一个字符串的出现位置时，常常会使用 KMP 算法，因为它在时间复杂度上具有优势。接下来，我将详细讲解 KMP 算法的原理和步骤。

假设我们需要在文本串 S 中查找模式串 P 的出现位置。

KMP 算法通过利用部分匹配表，可以在比较过程中跳过一些不必要的字符比较，提高了匹配的效率。这是因为部分匹配表保存了模式串 P 的前缀和后缀的最长相等长度，使得我们可以根据已经匹配到的字符信息，移动模式串 P 的位置，避免无效的比较操作。

构建 next 数组（也称为部分匹配表）是 KMP 算法的一部分，它用于预处理模式串 P。以下是一种常见的构建 next 数组的方法：

初始化 next 数组：创建一个长度为模式串 P 长度的数组，初始值都为 0。
遍历模式串 P，从第二个字符开始（即下标为 1），依次计算每个位置的最长相等前缀后缀长度。
对于第 i 个位置，首先令 j 等于前一个位置的 next 值，即 j = next [i-1]。
在一个循环中，比较模式串 P 的第 i 个字符和第 j 个字符：
- 如果 P [i] == P [j]，说明存在一个更长的相等前缀后缀，因此对应的 next [i] = j + 1，并将 i 和 j 分别向后移动一位（i++，j++）。
- 如果 P [i] != P [j]，说明当前字符不匹配，需要回溯。这时，j 指针需要根据已经计算得到的 next 数组来进行偏移，即 j = next [j]。
- 如果 j 已经回溯到开头（即 j=0），说明没有找到相等前缀后缀，此时对应的 next [i] 为 0，并将 i 向后移动一位（i++）。
重复步骤 4，直到遍历完整个模式串 P，得到最终的 next 数组。

下面举个例子来说明，假设模式串 P 为 "ABCDABD"：

通过以上步骤，我们成功地构建了 next 数组。在 KMP 算法的匹配过程中，利用这个数组可以根据已经匹配到的字符信息，移动模式串的位置，避免不必要的比较操作，提高匹配效率。

# 题目

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2

示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明：当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr () 以及 Java 的 indexOf () 定义相符。

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

	// 时间复杂度: O (n + m)
	// 空间复杂度: O (m), 只需要保存字符串 needle 的前缀表
	class Solution {
	public:
	void getNext(int* next, const string& s) {
	int j = -1;
	next[0] = j;
	for(int i = 1; i < s.size(); i++) { // 注意 i 从 1 开始
	while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
	j = next[j]; // 向前回退
	}
	if (s[i] == s[j + 1]) { // 找到相同的前后缀
	j++;
	}
	next[i] = j; // 将 j（前缀的长度）赋给 next [i]
	}
	}
	int strStr(string haystack, string needle) {
	if (needle.size() == 0) {
	return 0;
	}
	int next[needle.size()];
	getNext(next, needle);
	int j = -1; //// 因为 next 数组里记录的起始位置为 - 1
	for (int i = 0; i < haystack.size(); i++) { // 注意 i 就从 0 开始
	while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
	j = next[j]; //j 寻找之前匹配的位置
	}
	if (haystack[i] == needle[j + 1]) { // 匹配，j 和 i 同时向后移动
	j++; //i 的增加在 for 循环里
	}
	if (j == (needle.size() - 1) ) { // 文本串 s 里出现了模式串 t
	return (i - needle.size() + 1);
	}
	}
	return -1;
	}
	};

字符串 KMP