LeetCode28 实现strStr()(找到子串第一次出现的位置BF,KMP)
程序员文章站
2022-03-22 08:41:26
原题目代码分析使用c语言strstrchar *ch = strstr(haystack, needle) 得到当前位置int strStr(char * haystack, char * needle){ char * res = strstr(haystack, needle); return res!=NULL ? res-haystack : -1;}使用C++findint index = haystack.find(needle) 得到当前位置class So...
原题目
代码分析
使用c语言strstr
char *ch = strstr(haystack, needle) 得到当前位置
int strStr(char * haystack, char * needle){
char * res = strstr(haystack, needle);
return res!=NULL ? res-haystack : -1;
}
使用C++find
int index = haystack.find(needle) 得到当前位置
class Solution {
public:
int strStr(string haystack, string needle) {
return haystack.find(needle);
}
};
BF
class Solution {
public:
int strStr(string haystack, string needle) {
int index_h = 0, index_n = 0;//haystack的下标位置,needle的下标位置
while(index_h<haystack.size()&&index_n<needle.size()){
if(haystack[index_h] == needle[index_n]){//如果相等,继续比较下一个
index_h++;
index_n++;
}else{//如果不相等,则让haystack的下标移到上次起点的下一个,needle的下标从0开始
index_h = index_h - index_n + 1;
index_n=0;
if(haystack.size() - index_h < needle.size()){//如果haystack剩余的字符少于needle的字符数,则不能找到
break;
}
}
}
if(index_n == needle.size()){//如果needle遍历到最后,说明查找到了
return index_h - index_n;
}
return -1;
}
};
KMP
class Solution {
public:
void getNext(string n, vector<int>&next){
next[0] = -1;
int i = 0, j = -1;
while(i<n.size()){
if(j == -1|| n[i] == n[j]){
i++;
j++;
next[i] = j;
}else{
j = next[j];
}
}
}
int KMP(string h, string n){
vector<int>next(n.size()+1);
getNext(n,next);
int i = 0, j = 0;
while(i < (int)h.size()&& j < (int)n.size()){
if(j == -1 || h[i]==n[j]){
i++;
j++;
}else{
j = next[j];
}
}
return j == n.size()?i-j: -1;
}
int strStr(string haystack, string needle) {
return KMP(haystack, needle);
}
};
本文地址:https://blog.csdn.net/weixin_44529350/article/details/107279765