首页 线上实习 课程 找实习 必考题 咨询 专栏 组团学 稳拿计划
校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > KMP
题目

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

A.O(m)

B.O(n)

C.O(m*n)

D.O(nlog2m)

上一题 下一题
解答

正确答案是 A

KMP算法时间复杂度为O(m+n)，空间复杂度为O(m)。 因为KMP算法涉及到next数组的存储，且next数组是基于模式串长度计算的。
C 7条回复 评论
无畏无所畏

真棒！茅塞顿开的感觉。

发表于 2023-02-06 23:00:00
0 0
胡俟

准备三刷这节课！

发表于 2021-12-07 17:20:00
0 0
小茉莉

KMP算法时间复杂度为O（m+n），空间复杂度为O（m）

发表于 2019-07-15 20:46:18
1 0
二大爷 :

空间复杂度怎么理解？

发表于 2019-07-15 20:46:18
回复
回复
窦先生

普通匹配算法：时间复杂度O(m*n)；空间复杂度O(1)
KMP算法：时间复杂度O(m+n)；空间复杂度O(n)

发表于 2018-10-13 11:52:48
0 0
子不语

KMP算法所需的附加空间，即next数组所需的存储空间，等于模式串的长度O(m)

发表于 2018-10-13 11:52:40
0 0
遇见

A
KMP算法的控件复杂度为保存next数组的控件，next数组是对模式串计算的，大小为O(m)

发表于 2018-10-13 11:52:27
0 0
寒山远火

BF算法（普通匹配算法）：时间复杂度O(m*n)；空间复杂度O(1)
KMP算法：时间复杂度O(m+n)；空间复杂度O(n)

发表于 2018-10-13 11:52:17
0 0
问题信息
分类：数据结构 - KMP
难度:
最新校招难题刷题，快来进刷题群吧
相关试题