LeetCode 28.实现strStr() 暴力匹配与KMP-阿南达文事网

LeetCode 28.实现strStr() 暴力匹配与KMP

实现strStr

- 题目
- 题目分析
- - 思路一数组遍历
  - 思路二字符串分割
  - 思路三 KMP算法
- 详细代码
- - 思路一实现
  - 思路二实现
  - 思路三实现
- 总结

题目

给你两个字符串 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）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目分析

思路一数组遍历

当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=0if(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;}}
};

关于compare函数的用法

思路三实现

具体代码和执行结果，我放总结里面了。

总结

思路一和思路二均为暴力匹配的方法，只是在官方给出的解题方法上做了一些改进，不同在于我的两种思路使用的都是单层循环，官方就是无脑两层循环

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
链接：/
来源：力扣（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
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

LeetCode 28.实现strStr() 暴力匹配与KMP