给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
class Solution {
public:
void build_next(vector<int> &next,string str){
const int len = str.size();
next[0] = 0;
int i = 1;
int prefix_len = 0;
while(i < len){
if(str[i] == str[prefix_len]){
prefix_len++;
next[i] = prefix_len;
i++;
}else{
if(!prefix_len){
next[i] = 0;
i++;
}else{
prefix_len = next[prefix_len - 1];
}
}
}
return;
}
int strStr(string haystack, string needle) {
const int len = haystack.size();
next.resize(len);
//构建next数组
build_next(next,haystack);
//根据next数组进行kmp
int i = 0;
int j = 0;
while(i < len){
if(haystack[i] == needle[j]){
i++;
j++;
}else if(j > 0){
j = next[j - 1];
}else{
i++;
}
if(j == needle.size()){
return i - j;
}
}
return -1;
}
private:
vector<int> next;
};