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

[问答题]

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

张小头

因为kmp算法的时间复杂度包含求next数组的时间和复杂度和利用next数组去匹配正文串的时间复杂度，求next的时间复杂度是循环模式串的长度次数，也就是m，匹配正文串的时间复杂度是循环正文串长度次数，即n，所以总的时间复杂度是O(m+n)。

发表于 2021-02-17 17:29:50 回复(0)

杨😗

O(m+n)

发表于 2020-04-27 17:07:41 回复(0)

笑对人生651401001

O（m+n）

编辑于 2019-10-28 10:58:19 回复(0)

五尺六寸

O(m+n)

发表于 2019-10-27 21:57:15 回复(0)

提交观点

问题信息

字符串

上传者：城市里的养猫者

难度：

4条回答 3收藏 8801浏览

扫一扫，把题目装进口袋