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;

    }

};