Leetcode经典题15-- 找出字符串中第一个匹配项的下标（KMP）
题目描述：
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
输入输出示例：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。
解决方案
方式一：暴力求解法 （较优解）
算法思想：直观的解法的是：枚举原串 ss 中的每个字符作为「发起点」，每次从原串的「发起点」和匹配串的「首位」开始尝试匹配：
匹配成功：返回本次匹配的原串「发起点」。
匹配失败：枚举原串的下一个「发起点」，重新尝试匹配。
实现代码：
class Solution {
public int strStr(String ss, String pp) {
int n = ss.length(), m = pp.length();
char[] s = ss.toCharArray(), p = pp.toCharArray();
// 枚举原串的「发起点」
for (int i = 0; i <= n - m; i++) {
// 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
int a = i, b = 0;
while (b < m && s[a] == p[b]) {
a++;
b++;
}
// 如果能够完全匹配，返回原串的「发起点」下标
if (b == m) return i;
}
return -1;
}
}复杂度分析
时间复杂度：n 为原串的长度，m 为匹配串的长度。其中枚举的复杂度为 O(n−m)，构造和比较字符串的复杂度为 O(m)。整体复杂度为 O((n−m)∗m)。
空间复杂度：O(1)。
方式二：KMP算法
KMP算法-----大串当中找小串
KMP：找最长相等的前后缀组成的前缀表 O(m+n)
1.前缀和后缀
前缀：不包含最后一个字符的所有以第一个字符开头的连续字符串
后缀：不包含第一个字符的所有以最后一个字符结尾的连续字符串
2.找最长相等的前后缀组成的前缀表
3.KMP算法执行过程
第一步:两个游标从前向后进行变量，并且比较值是否相等，如果相等执行i++j++。
如果不相等，那么则和暴力解法不—致!
第二步:如果我们此时能够让i游标不动，同时j游标指向b是最好的。
如何指向b?
1.找前缀，后缀
2.找到最长相等前后缀的长度
3.利用前缀表重新匹配并构造next数组
很多KMP算法的实现都是使用next数组来做回退操作，那么next数组与前缀表有什么关系呢?
next数组就可以是前缀表，但是很多实现都是把前缀表统一减一(右移一位，初始位置为-1)之后作为next数组。
这并不涉及到KMP的原理，而是具体实现，next数组既可以就是前缀表，也可以是前缀表统一减一(右移一位，初始位置为-1)
next数组的构建过程
j=next[j-1] :将j指针返回到上一次最长相等前缀的末尾，再逐渐缩短前缀的长度，看是否能找到公共前缀，否则，将next数组的对应位置置0
第三步：
寻找匹配的下标
首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在，则跳转到「前缀」的下一个位置继续往下匹配：
跳转到下一匹配位置后，尝试匹配，发现两个指针的字符对不上，并且此时匹配串指针前面不存在相同的「前缀」和「后缀」，这时候只能回到匹配串的起始位置重新开始：
代码实现：
class Solution {
// KMP 算法
// ss: 原串(string) pp: 匹配串(pattern)
public int strStr(String ss, String pp) {
if (pp.isEmpty()) return 0;
// 分别读取原串和匹配串的长度
int n = ss.length(), m = pp.length();
// 原串和匹配串前面都加空格，使其下标从 1 开始
ss = " " + ss;
pp = " " + pp;
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
// 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
int[] next = new int[m + 1];
// 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
for (int i = 2, j = 0; i <= m; i++) {
// 匹配不成功的话，j = next(j)
while (j > 0 && p[i] != p[j + 1]) j = next[j];
// 匹配成功的话，先让 j++
if (p[i] == p[j + 1]) j++;
// 更新 next[i]，结束本次循环，i++
next[i] = j;
}
// 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
for (int i = 1, j = 0; i <= n; i++) {
// 匹配不成功 j = next(j)
while (j > 0 && s[i] != p[j + 1]) j = next[j];
// 匹配成功的话，先让 j++，结束本次循环后 i++
if (s[i] == p[j + 1]) j++;
// 整一段匹配成功，直接返回下标
if (j == m) return i - m;
}
return -1;
}
}复杂度分析：
时间复杂度：n 为原串的长度，m 为匹配串的长度。复杂度为 O(m+n)。
空间复杂度：构建了 next 数组。复杂度为 O(m)。
本文章主要参考Leetcode中宫水三叶老师的解法