问题描述
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出
needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack
的一部分，则返回 -1。
示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
1 <= haystack.length, needle.length <= 10⁴haystack和needle仅由小写英文字符组成
解题思路
标准的kmp算法模板题。
代码
class Solution {
public:
void SetNext(vector<int> &next, string needle) {
int x = 1, now = 0;
while (x < needle.size()) {
if (needle[x] == needle[now]) {
next[x++] = ++now;
} else if (now != 0) {
now = next[now - 1];
} else {
next[x] = 0;
x += 1;
}
}
}
int strStr(string haystack, string needle) {
int m = needle.size(), n = haystack.size();
vector<int> next(m);
SetNext(next, needle);
int i = 0, j = 0;
while (i < n && j < m) {
if (haystack[i] == needle[j]) {
++i;
++j;
} else {
if (j > 0) {
j = next[j - 1];
} else {
++i;
}
}
}
if (j >= m) {
return i - m;
}
return -1;
}
};