28. 找出字符串中第一个匹配项的下标

难度中等1835

给你两个字符串 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 <= 104

haystack和 needle仅由小写英文字符组成

第一种对法:

暴力，时间复杂度O(n*m),空间复杂度O(1)

第二种对法：

kmp算法,时间复杂度O（n+m），空间复杂度O(m)

思路：kmp算法最重要的部分就是next数组，如何得到next数组。

i:表示后缀末尾，j:表示前缀末尾

第一步：初始化

将j设置为0，将next[0]=0；

第二步：当条件是前后缀不相同时

while(int j=1;j<s.size();j++){

j = next[j-1];

}

第三步：当条件是前后缀相同时

if(s[i]==s[j])j++;

第四步：更新next数组

next[i]=j;

代码如下：

class Solution {

public:

void getNext(int *next,const string& s){

int j = 0;

next[0] = 0;

for(int i = 1;i<s.size();i++){

while(j>0 && s[i]!=s[j]){

j = next[j-1];

}

if(s[i]==s[j])j++;

next[i] = j;

}

}

int strStr(string haystack, string needle) {

if(needle.size()==0)return 0;

int next[needle.size()];

getNext(next,needle);

int j = 0;

for(int i = 0;i<haystack.size();i++){

while(j>0 && haystack[i] != needle[j]){

j = next[j-1];

}

if(haystack[i]==needle[j]){

j++;

}

if(j==needle.size())return (i - needle.size() + 1);

}

return -1;

}

};