KMP 算法真的是…看了忘，忘了看…每次看时都要从盘古开天辟地开始看…从大一看到现在，真·从小看到大！

本文题目难度标识：🟩简单，🟨中等，🟥困难。

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

模式匹配指的是求子串（模式串）在主串中的位置。常见的字符串匹配算法包括暴力匹配、Knuth-Morris-Pratt 算法、Boyer-Moore 算法、Sunday 算法等。

下文中，有时候将题目中的主串 haystack 称为 S，模式串 needle 称为 T。

暴力算法（Brute Force, BF）

每次匹配失败，T 串向前走。直到匹配成功或返回 -1。

我们发现，指向 S 和 T 串的指针，在出现失配时需要进行回溯。

public int strStr(String haystack, String needle) {
	int n = haystack.length(), m = needle.length();
	for (int i = 0; i + m <= n; i++) {
		boolean flag = true;
		for (int j = 0; j < m; j++) {
			// 加速点：发生不匹配时立即终止。
			if (haystack.charAt(i + j) != needle.charAt(j)) {
				flag = false;
				break;
			}
		}
		if (flag) {
			return i;
		}
	}
	return -1;
}

时间复杂度（最坏）： $O(n×m)$ ，其中 n 是字符串 haystack 的长度，m 是字符串 needle 的长度。最坏情况下我们需要将字符串 needle 与字符串 haystack 的所有长度为 m 的子串均匹配一次。

空间复杂度： $O(1)$ 。我们只需要常数的空间保存若干变量。

KMP 算法（Knuth-Morris-Pratt）

不正经简记：👁️🎩🎬

Knuth-Morris-Pratt 算法，简称 KMP 算法，由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三人于 1977 年联合发表。

一些定义：

真前缀：除最后一个字符以外，字符串的所有头部子串
真后缀：除第一个字符以外，字符串的所有尾部子串
部分匹配值（Partial Match）：字符串的前缀和后缀的最长相等前后缀长度

上图中：

上一串表示 S 串，下一串表示 T 串
红色表示失配点
蓝色和绿色表示匹配成功的部分
蓝色表示前后缀相同的部分

失配后将子串这样移，再进行后续的比较：

我们发现整个过程中主串指针 i 不需要回退。

Knuth-Morris-Pratt 算法的核心为前缀函数，记作 $π(i)$ ，其定义如下：对于长度为 L 的字符串 s，其前缀函数 $π(i)(0≤i<L)$ 表示 s 的子串 s[0:i] 的最长的相等的真前缀与真后缀的长度。特别地，如果不存在符合条件的前后缀，那么 $π(i)=0$ 。其中真前缀与真后缀的定义为不等于自身的的前缀与后缀。

字符串	a	a	b	a	a	a	b
`index`	0	1	2	3	4	5	6
$π(i)$ 、`next`	0	1	0	1	2	2	3

由 $π(i)$ 构成的表项我们也可以称为前缀表 next，含义在于当出现失配时，T 串需要回退的位置。

在子串的某一个字符 t[j] 处匹配失败时，我们需要查找该字符前面的那个子串的最大相等前后缀的长度，即 next[j-1]，然后使 j 指针退回到 next[j-1]，i 指针不变，继续匹配，不断重复这个操作直到匹配成功或者 j 指针大于等于子串长度。

在理解了前缀表及其作用之后，KMP 算法就可以整体上分为两步：

计算前缀表。我们可以一边读入字符串，一边求解当前读入位的前缀函数。
根据前缀表移动两个指针进行匹配。

public int strStr(String haystack, String needle) {
	return strStr1(haystack.toCharArray(),needle.toCharArray());
}

//这个函数对字符串s进行预处理得到next数组
public static void get_Next(char[] s, int[] next)		
{
	int j = 0;
	next[0] = 0;	//初始化
	// i指针指向的是后缀末尾，j指针指向的是前缀末尾
	for(int i = 1; i<s.length; i++){	
		while (j>0 && s[i]!=s[j])	
			j = next[j-1];	//前后缀不相同，循环找j前一位的最长相等前后缀
		if(s[i]==s[j])	j++;	//前后缀相同，j指针后移
		next[i] = j;	//更新 next 数组
	}
}

//这个函数是从s中找到t，如果存在返回t出现的位置，如果不存在返回-1
public int strStr1(char[] s, char[] t) {
	int[] next = new int[t.length];
	if(t.length==0)	return 0;
	get_Next(t, next);
	for(int i = 0,j = 0; i < s.length; i++){
		while(j>0 && s[i]!=t[j])
			j = next[j-1];	
		if(s[i]==t[j])	j++;
		if(j==t.length)	return i - t.length + 1;
	}
	return -1;
}