题目:
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()
赋值给新的变量保存,不然会出错: