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

站在用戶的角度思考問題，與客戶深入溝通，找到隨州網(wǎng)站設(shè)計與隨州網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設(shè)計與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：成都做網(wǎng)站、成都網(wǎng)站設(shè)計、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、域名注冊、網(wǎng)頁空間、企業(yè)郵箱。業(yè)務(wù)覆蓋隨州地區(qū)。

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

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

示例 1:

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

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

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

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

解題思路：

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

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

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

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

代碼實現(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)容，你們對kmp怎樣實現(xiàn)strstr() 函數(shù)有進(jìn)一步的了解嗎？如果還想了解更多知識或者相關(guān)內(nèi)容，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。

新聞標(biāo)題：kmp怎樣實現(xiàn)strstr()函數(shù)
路徑分享：http://jinyejixie.com/article22/podpjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計公司、、域名注冊、建站公司、軟件開發(fā)、網(wǎng)站排名

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)