力扣-字符串-28 找出字符串中第一个匹配项的下标
思路
kmp算法的练习，实际上来说在构建next数组和使用next数组都用到了前一位字符串的最长相等前后缀
代码
class Solution {
public:
void getNext(int *next, string s){
int j = 0;
next[0] = 0;
for(int i = 1; i < s.size(); i++){
while(j > 0 && s[j] != s[i]){
j = next[j - 1];
}
if(s[j] == s[i]) j++;
next[i] = j;
}
}
int strStr(string haystack, string needle) {
if(needle.size() == 0)
return 0;
vector<int> next(needle.size());
getNext(&next[0], needle);
int i = 0, j = 0;
for(int i = 0; i < haystack.size(); i++){
while(j>0 && needle[j] != haystack[i]){
j = next[j-1];
}
if(needle[j] == haystack[i]) j++;
if(j == needle.size()){
return i - j + 1;
}
}
return -1;
}
};