题目描述：
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
来源：力扣（LeetCode）
KMP算法理解：循环比较中，主子符串的位置是不回退的；就是每次回退比较 子字符串中的内容；先将最大的 公共前后缀重叠，如果不对，就以该不符合的点为界限，继续搜寻该点之前的最大公共前后缀！
解题重要步骤：
①正确的创建 next数组（等同于前缀表）；
②使用for循环遍历主字符串，结合next数组进行 遍历对比。
KMP学习：
kmp算法的理解：
相比于暴力，降低比较的次数；
①在出现不匹配的字符处，主字符串S和子字符串P一部分内容是对照的；默认为字符数组，如图：
S[1] 与P[0]对比，明显不可能成功；S[2]与P[0]也不能成功 ！
下次比较的时候，尝试跳过不可能成功的尝试！
引出next数组：也就是找最大的相等的前后缀（在子字符串中找），实际还是为了下次比较时，用子字符串的前缀 抵消掉 主字符串中 到 不匹配处之前的后缀！也就是匹配上了，不需要再进行比较，直接从原来不匹配处继续比较！
②next数组：就是记录最大相同前后缀的长度：如下所列
③最重要：next数组的构建：在P字符串中自己与自己匹配对比：其实等价于与S主字符串比较了
next[i] 就是 i位置上的，之前子串的最大相等前缀的长度；落在了第一个不相等的位置；如上next[4]就等于2，落在了 b 字符处！
则 不断往后计算时，
一个重要的对比：前缀必然包含子串头；后缀必然包含子串尾！
1）如果 P[x] = P[next[x-1]] ,就直接加1，next[x] = now + 1;此时的now就等于next[x-1]；
2）如果不相等，就将原来的 前缀作为一个串，找到他的最大相等的前缀，把now更新，now = next[now - 1]继续比较；不断迭代往前；
3）now最终只能回到 0 处，不能再往前！
next数组的构建：
for循环：
int size = s.length();
int[] next = new int[size];
int now = 0;//此时代表的也是 next[0]的值，此时为0
//注意 now的值和 数组下标的对应关系；now刚好是最大公共前后缀后一位的位置！
for(int i = 1;i < size;i++){//从一开始构造
if(s.charAt(i) == s.charAt(now)){
now++;//now后移
next[i] = now;
}
//此时不相同了，就是后缀长度不能加1；甚至一个都没有；要循环回去
else if(now != 0){
//直接在上一个位置的 最大前后缀的字符串里 往前找
now = next[now - 1];
//此时后面 i 不能加1
//使用 while和此不一样
i--;
}
else{
//此时往前找到了头now = 0;并且还不相等，就是首位都不相等
next[i] = now;
}
}
while循环
int[] next = new int[p.length];
int now = 0;//其实就是第一个位置 index为0时，next数组的元素
int i = 1;
while(i < p.length){
//如果后缀加一，与前缀加一的位置相同，就在该位置的next 加以
if(p[i] == p[now]){
now++;
next[i] = now;
i++;
}
//如果加一不相等，且此时还没到最初的位置，则
else if(now != 0){
now = next[now - 1];
}
//如果已经到了头 就是p[i] != p[now] && now == 0
else{
next[i] = now;
i++;
}
}
思路：
1）暴力查找：每次后移一位，时间复杂度O(N * M)
2）KMP算法：每次跳跃多位，将不可能成功的情况排除！时间复杂度 O(N +M)
代码：
1）KMP算法：每一步详解写在了代码上
class Solution {
public int strStr(String haystack, String needle) {
if(needle.length() == 0) return 0;
char[] ne = needle.toCharArray();
int[] next = getNext(ne);//得到next数组
int j = 0;
for(int i = 0;i < haystack.length();i++){
//如果没匹配上
while(j > 0 && needle.charAt(j) != haystack.charAt(i)) j = next[j - 1];
//对上了，就后移，继续比较
if(needle.charAt(j) == haystack.charAt(i)) j++;
if(j == needle.length()) return i - needle.length() + 1;
}
return -1;//循环结束也没有找到合适的字串
}
//构建 next数组
int[] getNext(char[] p){
int[] next = new int[p.length];
int now = 0;//其实就是第一个位置 index为0时，next数组的元素
int i = 1;
while(i < p.length){
//如果后缀加一，与前缀加一的位置相同，就在该位置的next 加以
if(p[i] == p[now]){
now++;
next[i] = now;
i++;
}
//如果加一不相等，且此时还没到最初的位置，则
else if(now != 0){
now = next[now - 1];
}
//如果已经到了头 就是p[i] != p[now] && now == 0
else{
next[i] = now;
i++;
}
}
//得到的就是 next数组，要匹配的字符串的next数组
return next;
}
}
