28. C++ 实现 strStr() 也就是优化了大概4次那么多吧(KMP算法next+nextval)

【摘要】 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

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享