题目内容（请给出正确答案）

[单选题]

设串长为n，模式串长为m，则KMP算法所需的附加空间为（)。

A.O(m)

B.O(n)

C.O(m*n)

D.O(nlog2(m))

提问人：网友Chenshan2019 发布时间：2022-01-06

参考答案

查看官方参考答案

如搜索结果不匹配，请联系老师获取答案

网友答案

查看全部（）

· 有4位网友选择 A，占比23.53%
· 有3位网友选择 C，占比17.65%
· 有3位网友选择 B，占比17.65%
· 有3位网友选择 D，占比17.65%
· 有3位网友选择 C，占比17.65%
· 有1位网友选择 B，占比5.88%

ABCD

提交我的答案

登录提交答案，可赢取奖励机会。

您可能会需要：

重置密码查看订单联系客服

安装简答题APP，拍照搜题省时又省心！

更多“设串长为n，模式串长为m，则KMP算法所需的附加空间为（)。”相关的问题

第1题

设串长为n，模式串长为m，则KMP算法所需的附加空间为（)。

A、O(m)

B、O(n)

C、O(m*n)

D、O(nlog2(m))

点击查看答案

第2题

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

点击查看答案

第3题

设主串t的长度为n，模式串p的长度为m，则KMP算法的时间复杂度为O（n+m)

点击查看答案

第4题

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

A.O(m*n)

B.O(n)

C.O(m)

D.O(m+n)

点击查看答案

第5题

设主串长为n，模式串长为m（m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为（)A．mB．n-m

设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 ()

A．m

B．n-m

C．n-m+1

D．n

点击查看答案

第6题

设正文串长度为a，模式串长度为b，则串匹配的KMP算法的时间复杂度为O（a+b)。

点击查看答案

第7题

设主串长为n，模式串长为m(m≤n)，则在匹配失败的情况下，朴素匹配算法进行的无效位移次数为(30)。

A.m

B.n-m

C.n-m+1

D.n

点击查看答案

第8题

目标串的字符个数为n，模式串的字符个数为m，利用KMP算法进行模式匹配，其时间复杂度为O（____）。

点击查看答案

第9题

若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为（）。

点击查看答案

第10题

设主串t的长度为n，模式串p的长度为m，则BF算法的时间复杂度为O（n+m)

点击查看答案

第11题

（1）当算法中需要使用多个栈时，可以采用不同的存储结构来实现。试为这多个栈设计三种存储结构（语言

描述，不需要写代码）并说明这三种方案各自的优缺点；（10分）（2）已知主串S=‘abcaabbabcabaacbacba’,模式串T=‘bcabaa’,计算模式串T的 next 函数值、改进的nextval函数值以及匹配成功时的字符比较次数（利用改进的nextval值），最后分析KMP算法的时间效率（假设主串长m，模式串长n）并说明KMP算法相比朴素的模式匹配算法效率高的原因。（10分）

点击查看答案

警告：系统检测到您的账号存在安全风险

为了保护您的账号安全，请在“简答题”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！

微信搜一搜

简答题

点击打开微信

警告：系统检测到您的账号存在安全风险

抱歉，您的账号因涉嫌违反简答题购买须知被冻结。您可在“简答题”微信公众号中的“官网服务”-“账号解封申请”申请解封，或联系客服。

微信搜一搜

简答题

点击打开微信