题目
给你两个字符串 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 仅由小写英文字符组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-strstr
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目分析
思路一 数组遍历
- 当needle字符串为null时，return 0
- 当needle字符串不为null时，对haystack和needle两个字符串进行遍历
- 当haystack和needle字符串中的元素相同时，对下一个元素进行比较，直到将needle字符串遍历完
- 当haystack和needle字符串元素不同时，重新将haystack字符串当前元素的下一个元素和needle第一个元素进行比较
（2.中的两种情况构成了一个循环体）
思路二 字符串分割
将haystack字符串按照（ i, i+needle.length() ) ( 0 <= i < haystack.length()-needle.length() ) 长度进行分割，循环遍历与needle进行比较
思路三 KMP算法
KMP算法原理讲解（易懂版）
视频和官方的文章结合起来看，更容易理解。理解不了就自己举一个简单的例子，手推一下就能懂了。
详细代码
思路一实现
数组（C++实现）
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle=="") return 0;
else{
int i=0,j=0;
int flag = 0;
for(;i<haystack.length();i++){
if(haystack[i]==needle[j]) {
// 如果当前比较元素为needle字符串中的最后一个元素，跳出循环，令flag=1
if(j==needle.length()-1) {
flag =1;
break;
}
j++;
}else{
i = i-j;
j = 0;
}
}
// 如果循环结束时，是将haystack字符串遍历完且needle字符串没有遍历完时，flag=0
if(flag==1) return i-j;
else return -1;
}
}
};
思路二实现
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle=="") return 0;
else{
int i=0,flag =0;
for(;i<haystack.length();i++){
if(i<=haystack.length()-needle.length()){
// 分割子字符串
string tempStr=haystack.substr(i,needle.length());
if(tempStr == needle)
{
flag =1;
break;
}
}
// 这里不使用else，因为前面出现了两个if判断语句，使用else会出现歧义
if(i+needle.length()>haystack.length()){
break;
}
}
if(flag==0)
return -1;
else return i;
}
}
};
在这个解法中，我使用了tempStr来储存分割出来的子字符串，消耗了比思路一中更多的内存。为了降低内存的消耗，减少代码的执行时间，我使用compare函数对代码进行改进
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle=="") return 0;
else{
int i=0,flag =0;
for(;i<haystack.length();i++){
if(i+needle.length()>haystack.length()){
break;
}else{
if(needle.compare(0,needle.length(),haystack,i,needle.length())==0)
{
flag =1;
break;
}
}
}
if(flag==0)
return -1;
else return i;
}
}
};
思路三实现
具体代码和执行结果，我放总结里面了。
总结
- 思路一和思路二均为暴力匹配的方法，只是在官方给出的解题方法上做了一些改进，不同在于我的两种思路使用的都是单层循环，官方就是无脑两层循环
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
for (int i = 0; i + m <= n; i++) {
bool flag = true;
for (int j = 0; j < m; j++) {
if (haystack[i + j] != needle[j]) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 官方给出的第二种解题方法是KMP算法，我寻思什么时候KMP算法也是简单题的范畴了？！已经卷成这样了嘛？！用这个算法做出来，执行时间是挺好看的。
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
if (m == 0) {
return 0;
}
vector<int> pi(m);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] != needle[j]) {
j = pi[j - 1];
}
if (needle[i] == needle[j]) {
j++;
}
pi[i] = j;
}
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = pi[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
