【摘要】 28. 实现 strStr() 函数（STL \ 暴力 \ KMP算法next+nextval）
一、题目：
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明： 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面…
28. 实现 strStr() 函数（STL \ 暴力 \ KMP算法next+nextval）
一、题目：
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = “hello”, needle = “ll”
输出：2
示例 2：
输入：haystack = “aaaaa”, needle = “bba”
输出：-1
示例 3：
输入：haystack = “”, needle = “”
输出：0
提示：
0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成
二、思路代码和结果：
方法一：不讲武德之使用STL之明天来上班系列:
STL .find这个函数和这个题简直一摸一样，上手就是一行！
class Solution {
public: int strStr(string haystack, string needle) { //在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 return haystack.find(needle); }
};
方法二：朴素的一次遍历寻找
其实就是普通的搜索，符合我们第一眼看到题目时候的想法，至少是符合我的，哈哈：
1、使用needle在haystack中寻找，如果两个字符串字母相等，那么我们查找下一个
2、如果不相等的话，使用从needle第一个字符开始从（当前的haystack的位置减去needle当前的位置的下一个位置）开始查找。
3、 重复1和2直到两个字符串中任意一个到达结尾处。
class Solution {
public: int strStr(string haystack, string needle) { //如果needle为空，那么必然不可能在haystack中找到，直接返回0； if(needle.size()==0)return 0; //初始化i,j;其中 i是haystack的下标值，j是needle的下标值 int i=0,j=0; while(j<needle.size() && i<haystack.size()){ //如果两个元素相等查找下一个 if(haystack[i]==needle[j]){ i++,j++; }
//如果不相等的话，使用从needle第一个字符开始从（当前的h的位置减去n当前的位置的下一个位置）开始查找。 else{ i=i-j+1; j=0; } }//因为最后返回的值是needle的最开始的位置，所以有： //如果j指向了needle的最后一个元素，说明找到了 if(j==needle.size()){ //返回haystack 字符串中找出 needle 字符串出现的第一个位置 return i-j; } else return -1;//没找到，返回-1 }
};
方法三： 朴素的KMP（烤馍片算法？？？）
弄懂上面的方法后，我们不难发现，在一些比较中，我们进行了一些重复的工作。 例如：haystack为”abcdefgh”，needle为“abab”;因为needle中前后的ab和ab是一样的，所以我们在比到第二个a和haystack中的c不等的时候，不必再用方法二中的使用needle的第一个开头a和haystack中的b比较了，肯定不相等嘛，直接从c开始比。反复思考一下这里，很重要，这个是算法可以改进的点。
具体的办法就是我们额外的开辟一个next数组空间存储我们下一次应该从哪里开始查找。
//第一版KMP:
class Solution {
public: vector<int> get_next(string needle){ int len =needle.size(); vector<int>next(len+1,0); //子串取-1开始 int i=-1,j=0; next[0]=-1; while(j<len){ if(i==-1 || needle[i]==needle[j]){// i++;j++; next[j] = i; } //如果不相等，使用j=-1推动向前 else{ i=next[i]; } } return next; } int strStr(string haystack, string needle) { int len =needle.size(); vector<int>next = get_next(needle); int i=0,j=0; while(j<len && i<haystack.size()){ if(j==-1 || haystack[i]==needle[j]){ i++,j++; } else{//如果不相等，使用next数组,用j=-1推动向前 j = next[j]; } } if(j==len){ return i-j; } return -1; }
};
举个例子：
needle ="a b c a b x";
next[] =-1 0 0 0 1 2
方法四：nextval版
在方法三的基础上： 在方法三中，多次因为i==-1而循环，所以考虑是否能够省去这些步骤，具体实现如下：
class Solution {
public: vector<int> get_nextval(string needle){ int len =needle.size(); vector<int>next(len+1,0); //子串取-1开始 int i=-1,j=0; next[0]=-1; while(j<len){ if(i==-1 || needle[i]==needle[j]){// i++;j++; //########## 改进↓↓↓↓↓↓↓ ######## //区分needle[i]和needle[j]是否相等,可以省去因为i==-1而多进行的循环 //如果needle[i]==needle[j],next[j] = next[i] //否则将i的值给next[j] if(needle[i]==needle[j]) next[j] = next[i]; else next[j] =i; //########## 改进 ↑↑↑↑↑↑↑ ######## } else{ i=next[i]; } } return next; } int strStr(string haystack, string needle) { int len =needle.size(); vector<int>next = get_nextval(needle); int i=0,j=0; while(j<len && i<haystack.size()){ if(j==-1 || haystack[i]==needle[j]){ i++,j++; } else{ j = next[j]; } } if(j==len){ return i-j; } return -1; }
};
还是那个例子：
needle ="a b c a b x";
next[] =-1 0 0 0 1 2
nextval[]=-1 0 0 -1 0 2
由上可知，如果采用方法3，那么在c和x不一样时候，应该从第二个b上开始比较，但是因为a不会和b相等，所以a直接和x相比，这样就又跳过了一些不必要的比较，至此，我想我是明白了这烤馍片（KMP）算法了。
脑细胞死无数个，我以后再也不想看到这个膜片了。嗯，我先去再趁热复写一次！
复写完了，对比观察提交结果发现KMP的空间占用好像比STL和纯暴力更高？纯暴力和STL的时间、空间占用都还不错？？？这让我感到很难受。有懂的大佬可以解释一下，因为KMP开辟了更多空间？
大声喊出那句话：怕什么真理无穷，进一步有进一步的欢喜！
文章来源: blog.csdn.net，作者：甜橙の学习笔记，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/sweetorange_/article/details/115960266
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
