溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
今天就跟大家聊聊有關kmp怎樣實現strstr() 函數，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。
實現 strStr() 函數。
給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從0開始)。如果不存在，則返回 -1。
示例 1:
輸入: haystack = "hello", needle = "ll"輸出: 2示例 2:輸入: haystack = "aaaaa", needle = "bba"輸出: -1說明:
當 needle 是空字符串時，我們應當返回什么值呢？這是一個在面試中很好的問題。
對于本題而言，當 needle 是空字符串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符
解題思路：
1，用暴力解法，時間復雜度是O（mn）
2，使用kmp算法是用空間換時間，用O（m）的空間可以獲得O（m＋n）的時間復雜度
3，next數組的作用：記錄當前的后綴字串與前綴子串最大匹配長度。已經比較過的地方可以不用比較
4，思想和dp很像，但是空間復雜度O（m）比dp O（mn）低
代碼實現
func strStr(haystack string, needle string) int {if haystack==needle || needle==""{return 0}if len(needle)==0{return -1}next:=getNext(needle)m:=0for 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:=0for 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}
看完上述內容，你們對kmp怎樣實現strstr() 函數有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
