LeetCode——28. Implement strStr()

时间:2024-08-26 08:05:37

题目:

LeetCode——28. Implement strStr()

class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()){
return 0;
} vector<int> next;
int i = 0;
int j = 0;
int sLen = haystack.size();
int tLen = needle.size(); next = getNext(needle); while((i<sLen)&&(j<tLen)){
if((j==-1)||(haystack[i]==needle[j])){
i++;
j++;
}
else{
j = next[j];
}
} if(j==tLen){
return i-j;
} return -1;
} vector<int> getNext(string pattern){
vector<int> next;
int j = -1;
int i = 0;
int len = pattern.size(); next.push_back(-1); while(i<len-1){
if(j==-1||pattern[i] == pattern[j]){
i++;
j++;
next.push_back(j);
}
else{
j = next[j];
}
}
return next;
}
};

思路:KMP算法,重点在getNext。KMP算法的话打算另外写,这里就不写了。

上面这个是未经过优化的,如果进行优化则:

    vector<int> getNext(string pattern){
vector<int> next;
int j = -1;
int i = 0;
int len = pattern.size(); next.push_back(-1); while(i<len-1){
if(j==-1||pattern[i] == pattern[j]){
i++;
j++;
if(pattern[j]!=pattern[i]){
next.push_back(j);
}
else{
next.push_back(next[j]);
}
}
else{
j = next[j];
}
}
return next;
}

就是当前缀和后缀相同的时候那么应该应该继续递归,因为相同字符没意义。

值得注意的是while((i<sLen)&&(j<tLen)),一定要先将needle.size()haystack.size()赋值给新的变量保存,不然会出错:

LeetCode——28. Implement strStr()