首页 > 试题广场 >

给定的一个长度为N的字符串str,查找长度为P(PN)的字

[单选题]
给定的一个长度为N的字符串str，查找长度为P(P<N)的字符串在str中的出现次数。下面的说法正确的是（） 
  • 不存在比最坏时间复杂度O(NP)好的算法
  • 不存在比最坏时间复杂度O(N^2)好的算法
  • 不存在比最坏时间复杂度O(P^2)好的算法
  • 存在最坏时间复杂度为O(N+P)的算法
  • 存在最坏时间复杂度为O(log(N+P))的算法
  • 以上都不对
查看答案及解析
添加回答
Whisper。头像 Whisper。
朴素匹配算法 时间复杂度O（(N-P+1)*P）
KMP匹配算法 时间复杂度为O（N+P）
发表于 2016-07-26 22:32:58 回复(0)
凌梦初辰头像 凌梦初辰
建议大家还是有空看看KMP算法，还有部分匹配值的计算。
还是很有用的。推荐大家一个博客，就是讲KMP的。
发表于 2017-09-25 22:54:08 回复(1)
akalaka头像 akalaka
kmp最坏时间复杂度应该是O(NP)，而通过kmp不能确定答案，而是考虑比kmp更好的bm和Sunday算法
发表于 2016-07-04 10:40:45 回复(5)
黏黏糖头像 黏黏糖
朴素的匹配算法，即每次向右挪一位，一共移动N-P+1次（初始算第一次），时间复杂度为O((N-P+1)*P)
KMP算法，时间复杂度为O(N+P)
发表于 2017-05-31 15:38:16 回复(0)
EdisonPan头像 EdisonPan
KMP算法:时间复杂度O(p+N)

发表于 2016-09-03 10:43:27 回复(0)
三生饺子头像 三生饺子
(106条消息) 从头到尾彻底理解KMP（2014年8月22日版）_next数组计算方法_v_JULY_v的博客-CSDN博客
发表于 2023-08-01 10:23:45 回复(0)
牛牛要炸了啊头像 牛牛要炸了啊
kmp
发表于 2022-10-24 20:57:54 回复(0)
Hum4n头像 Hum4n
kmp O(m+n)
发表于 2022-08-21 17:27:19 回复(0)
牛客801282807号头像 牛客801282807号
实际应用中一般bf也是p+n，一般比较多的情况下用kmp
发表于 2022-08-10 11:42:40 回复(0)
_321头像 _321
Hello
发表于 2021-12-05 11:44:40 回复(0)
哈士奇会打滚头像 哈士奇会打滚
<p>朴素匹配算法 时间复杂度O（(N-P+1)*P） </p><p> KMP匹配算法 时间复杂度为O（N+P）</p>
发表于 2020-06-19 16:02:10 回复(0)
呐1呐1呐头像 呐1呐1呐
kmp匹配算法
发表于 2020-02-29 17:37:55 回复(0)
我叫mx头像 我叫mx
最坏时间复杂度？
发表于 2017-08-03 01:57:05 回复(0)
雨点儿1991头像 雨点儿1991
在说KMP算法的时候不用考虑创建next数组的时间复杂度吗？
发表于 2017-04-24 16:01:54 回复(0)
等风来~~~~头像 等风来~~~~
d kmp时间复杂度为o（n+p）
发表于 2016-08-09 18:06:38 回复(0)
牛客7599801号头像 牛客7599801号
所以什么叫“最坏时间复杂度”答案理解无能
发表于 2016-08-03 17:08:50 回复(2)
牛太郎头像 牛太郎
最坏复杂度难道不是O(NP)?O(N+P）叫最坏吗？
发表于 2016-07-16 15:08:13 回复(1)
牛客9224710号头像 牛客9224710号
字符串查找算法
发表于 2016-06-28 11:25:46 回复(0)
huixieqingchun头像 huixieqingchun
KMP算法的时间复杂度为O(m+n)
发表于 2016-05-11 19:35:41 回复(0)
txlstars头像 txlstars
KMP 选项D
发表于 2016-05-08 15:20:31 回复(0)
提交观点

问题信息

查找
来自：阿里巴巴2017实习生...
难度：
21条回答 15086浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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