我要招人

去企业版

首页 > 试题广场 >

长为n的字符串中匹配长度为m的子串的复杂度为？

[单选题]

KMP算法下，长为n的字符串中匹配长度为m的子串的复杂度为（）

```
O(N)
```
```
O(M+N)
```
```
O(N+LOGM)
```
```
O(M+LOGN)
```

查看正确选项

April丶

简单匹配算法的时间复杂度为O(m*n)，KMP匹配算法时间复杂度为O(m+n).。

发表于 2017-09-15 11:24:18 回复(0)

张@恒

http://kb.cnblogs.com/page/176818/

发表于 2017-04-16 15:17:33 回复(1)

CharlesByrant

KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。 时间复杂度 O(m+n)。

发表于 2017-03-05 21:35:38 回复(0)

rppp

KMP算法：根据计算出的next数组，若当前不匹配，直接找到下一个匹配的位置，无需整体遍历一遍，时间复杂度为o(M+N)

发表于 2017-07-27 21:36:57 回复(0)

Tachone

KMP算法通过提前处理出的next数组，在发生不匹配时直接跳到下一个可能符合的位置，而不是一个个去遍历比较，时间复杂度为O(M+N)

发表于 2016-03-29 09:32:44 回复(0)

luwen2025

KMP模式匹配的话是B

发表于 2014-11-12 19:13:46 回复(0)

BrainerGao

KMP模式匹配的时间复杂度为O(m+n)。

发表于 2016-05-06 18:23:46 回复(2)

TuringYoung_01

KMP算法下，长为n的字符串中匹配长度为m的子串的复杂度为（）O(M＋N)

发表于 2019-06-22 01:23:00 回复(0)

TobeNO.1

一直都不太明白复杂度，都是背熟的。。。

发表于 2017-08-20 16:25:36 回复(1)

苔上雪告诉我

KMP算法：根据计算出的next数组，若当前不匹配，直接找到下一个匹配的位置，无需整体遍历一遍，时间复杂度为o(M+N)

发表于 2017-08-13 22:19:42 回复(0)

尼见

看了看kmp算法的实现，复杂度确实是o(m+n)

发表于 2016-05-18 16:21:33 回复(0)

牛客606231号

应该是将计算next数组也算上了

发表于 2016-04-16 22:59:00 回复(0)

天字第一号

发表于 2016-03-29 16:13:57 回复(0)

BearFYB

B，借助于由匹配串计算的next数组，主串不会只会遍历一遍，匹配串存在多次重置匹配的操作。看毛片的话，O（M+N）就够了。

发表于 2016-03-29 10:26:20 回复(0)

牛客246012号

http://wapbaike.baidu.com/view/659777.htm?fr=aladdin&ref=wise&ssid=0&from=1000716a&uid=0&pu=usm@0,sz@1320_1001,ta@iphone_2_4.4_3_537&bd_page_type=1&baiduid=C37A06ACBF04296194116419636E0294&tj=Xv_1_0_10_l1

发表于 2015-10-29 08:12:41 回复(0)

生命的力量

http://baike.baidu.com/link?url=2dOT1JiiXYkVl1OL7vvKSvSNm7wxw0UOhb47blUQSar6eJxRqoOyH-wK9PHIt_jV0IP-bJgVzbR57XWifbJ9E _

发表于 2015-08-31 21:26:28 回复(3)

徐行

什么是kmp模式？

发表于 2015-08-06 00:29:50 回复(1)

royad

发表于 2015-04-02 10:55:21 回复(0)

提交观点

问题信息

字符串复杂度阿里巴巴

上传者：跳槽专家

难度：

18条回答 1339收藏 21614浏览

长为n的字符串中匹配长度为m的子串的复杂度为？

问题信息

热门推荐

相关试题