首页 > 试题广场 >

设正文串长度为n，模式串长度为m，则串匹配的KMP算法时间复

[问答题]

设正文串长度为n，模式串长度为m，则串匹配的KMP算法时间复杂度为（）

添加回答
张小头头像 张小头
因为kmp算法的时间复杂度包含求next数组的时间和复杂度和利用next数组去匹配正文串的时间复杂度，求next的时间复杂度是循环模式串的长度次数，也就是m，匹配正文串的时间复杂度是循环正文串长度次数，即n，所以总的时间复杂度是O(m+n)。
发表于 2021-02-17 17:29:50 回复(0)
杨😗头像 杨😗
O(m+n)
发表于 2020-04-27 17:07:41 回复(0)
笑对人生651401001头像 笑对人生651401001
O（m+n）
编辑于 2019-10-28 10:58:19 回复(0)
五尺六寸头像 五尺六寸
O(m+n)
发表于 2019-10-27 21:57:15 回复(0)
提交观点

问题信息

字符串
上传者：城市里的养猫者
难度：
4条回答 9244浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号