KMP求模式值的复杂度为什么是O(m)?
收起
知与谁同
2018-07-16 14:48:55
2515
0
2
条回答
写回答
取消
提交回答
-
假设模式串的长度为m,而next数组是这样对模式串进行处理的:对每个index i,都找next[i - 1]或者next[next[i -1]]去判断下标 i 这个位置的数字应该是多少,所以总体就是一个下标“一次”运算,总共有m个,所以算next的时间复杂度是O(m)。
2019-07-17 22:55:53
-
算法复杂度是o(m),而是o(m+n)
如果从字符串S中匹配字符串T
要先对T进行遍历,求一个next数组
根据next数组匹配的时候,
当出现 Si != Tj时,下一次的比较应该是Si和T next[j]进行比较,不需要回溯
因此,时间复杂度O( strlen(s) + strlen(t))
2019-07-17 22:55:53