Go 刷 Leetcode 系列：经典（8） kmp 实现strstr（）

vlambda
2020-07-13

Go 刷 Leetcode 系列：经典（8） 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:=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}