溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

kmp怎樣實(shí)現(xiàn)strstr() 函數(shù)

發(fā)布時(shí)間：2021-12-09 16:46:44 來源：億速云 閱讀：121 作者：柒染 欄目：大數(shù)據(jù)

今天就跟大家聊聊有關(guān)kmp怎樣實(shí)現(xiàn)strstr() 函數(shù)，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

實(shí)現(xiàn) strStr() 函數(shù)。

給定一個(gè) haystack 字符串和一個(gè) needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開始)。如果不存在，則返回  -1。

示例 1:

輸入: haystack = "hello", needle = "ll"輸出: 2示例 2:

輸入: haystack = "aaaaa", needle = "bba"輸出: -1說明:

當(dāng) needle 是空字符串時(shí)，我們應(yīng)當(dāng)返回什么值呢？這是一個(gè)在面試中很好的問題。

對(duì)于本題而言，當(dāng) needle 是空字符串時(shí)我們應(yīng)當(dāng)返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符

解題思路：

1，用暴力解法，時(shí)間復(fù)雜度是O（mn）

2，使用kmp算法是用空間換時(shí)間，用O（m）的空間可以獲得O（m＋n）的時(shí)間復(fù)雜度

3，next數(shù)組的作用：記錄當(dāng)前的后綴字串與前綴子串最大匹配長度。已經(jīng)比較過的地方可以不用比較

4，思想和dp很像，但是空間復(fù)雜度O（m）比dp O（mn）低

代碼實(shí)現(xiàn)

func strStr(haystack string, needle string) int {     if haystack==needle || needle==""{         return 0     }     if len(needle)==0{        return -1    }    next:=getNext(needle)    m:=0    for i:=0;i<len(haystack);i++{        for m>0 && haystack[i]!=needle[m]{            m=next[m-1]        }        if haystack[i]==needle[m]{            m++            if m==len(needle){                return i-m+1            }        }    }    return -1}
func getNext(needle string)[]int{    next:=make([]int,len(needle))    i:=0    for j:=1;j<len(needle);j++{        for i>0 && needle[i]!=needle[j]{          i=next[i-1]        }        if needle[j]==needle[i]{            i++        }        next[j]=i    }    return next}

看完上述內(nèi)容，你們對(duì)kmp怎樣實(shí)現(xiàn)strstr() 函數(shù)有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手