28. 找出字符串中第一個(gè)匹配項(xiàng)的下標(biāo)

難度中等1835

給你兩個(gè)字符串?haystack?和?needle?，請(qǐng)你在?haystack?字符串中找出?needle?字符串的第一個(gè)匹配項(xiàng)的下標(biāo)（下標(biāo)從 0 開始）。如果?needle?不是?haystack?的一部分，則返回??-1?。

?

示例 1：

輸入：haystack = "sadbutsad", needle = "sad"輸出：0解釋："sad" 在下標(biāo) 0 和 6 處匹配。 第一個(gè)匹配項(xiàng)的下標(biāo)是 0 ，所以返回 0 。

示例 2：

輸入：haystack = "leetcode", needle = "leeto"輸出：-1解釋："leeto" 沒有在 "leetcode" 中出現(xiàn)，所以返回 -1 。

?

提示：

• 1 <= haystack.length, needle.length <= 104

• haystack?和?needle?僅由小寫英文字符組成

第一種對(duì)法:

暴力，時(shí)間復(fù)雜度O(n*m),空間復(fù)雜度O(1)

第二種對(duì)法：

kmp算法,時(shí)間復(fù)雜度O（n+m），空間復(fù)雜度O(m)

思路：kmp算法最重要的部分就是next數(shù)組，如何得到next數(shù)組。

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

第一步：初始化

將j設(shè)置為0，將next[0]=0；

第二步：當(dāng)條件是前后綴不相同時(shí)

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

? ? j = next[j-1];

}

第三步：當(dāng)條件是前后綴相同時(shí)

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

第四步：更新next數(shù)組

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;

????}

};