设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。__N诺考研

登录注册上岸

学习人数: 15.6k

正确率: 62%

未通过

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

A. O(m) B. O(n) C. O(m*n) D. O(nlog₂m)

上面问题的答案是：

A A 选项

B B 选项

C C 选项

D D 选项

个人笔记

已有59条笔记

加入错题本

提示

提示内容

登录后提交答案

3 个回答 (点击展开回答)

2025年6月12日 20:49

A

因为KMP算法涉及到next数组的存储，next数组是基于模式串长度计算的

赞(1)

2021年9月8日 15:24

A

因为KMP算法涉及到next数组的存储，next数组是基于模式串长度计算的。

赞(1)

chenguangjie

2021年6月11日 17:55

KMP算法的空间复杂度应该为O(m),因为需要存储next数组计算值

赞(1)