力扣-字符串-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;}
};