平武建站

kmp怎样实现strstr()函数

今天就跟大家聊聊有关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() 函数有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注创新互联行业资讯频道，感谢大家的支持。


当前名称：kmp怎样实现strstr()函数
转载来源：http://pwwzsj.com/article/podpjc.html

其他资讯