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