力扣精选top面试题-------- 实现 strStr()

思路：
这道题就用双指针来做，这是比较简单的做法，还有一种就是KMP的做法

代码：

class Solution {
public:
int strStr(string haystack, string needle) {
if ( needle == "" )
//空则返回0
return 0;
int hlen = haystack.length();
int nlen = needle.length();
int i,j;
for(i=0;i<hlen;i++){
for(j=0;j<nlen;j++)
if(haystack[i+j]!=needle[j])
break;
//不符合就结束本轮匹配
if(j==nlen)
return i;
}
return -1;
}
};

KMP：

class Solution {
public:
int strStr(string haystack, string needle) {
int len = haystack.size();
int lenb
= needle.size();
if(len==0 && lenb==0)
return 0;
else if(len==0 && lenb!=0)
return -1;
else if(len!=0 && lenb==0)
return 0;
int ne[lenb]={0};
ne[0]=-1;
//int lenb
= needle.size();
for(int i=1,j=-1;i<lenb;++i){
while(j!=-1 && needle[i]!=needle[j+1])
j = ne[j];
if(needle[i]==needle[j+1])
++j;
ne[i] = j;
}
for(int i=0,j=-1;i<len;++i){
while(j!=-1 && haystack[i]!=needle[j+1])
j = ne[j];
if(haystack[i]==needle[j+1])
++j;
if(j==lenb-1){
return i-j;
}
}
return -1;
}
};

最后

以上就是阔达音响为你收集整理的力扣精选top面试题-------- 实现 strStr()的全部内容，希望文章能够帮你解决力扣精选top面试题-------- 实现 strStr()所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。