十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
今天就跟大家聊聊有关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
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
for i>0 && needle[i]!=needle[j]{
i=next[i-1]
}
if needle[j]==needle[i]{
i++
}
next[j]=i
}
return next
}
看完上述内容,你们对kmp怎样实现strstr() 函数有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注创新互联行业资讯频道,感谢大家的支持。