题目内容
（请给出正确答案）
提问人：网友sxz168
发布时间：2022-01-07
[主观题]
设主串t的长度为n，模式串p的长度为m，则KMP算法的时间复杂度为O（n+m)
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
抱歉！暂无答案，正在努力更新中……
网友您好，请在下方输入框内输入要搜索的题目：
搜题
题目内容
（请给出正确答案）
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
抱歉！暂无答案，正在努力更新中……
更多“设主串t的长度为n，模式串p的长度为m，则KMP算法的时间复杂度为O（n+m)”相关的问题
第2题
已知字符串 S 为 “abaabaabacacaabaabcc” ，模式串 t 为 “abaabc” 。采用 KMP 算法进行匹配，第一次出现 “失配” （ s[i] ≠ t[j] ）时，i = j = 5，则下次开始匹配时，i 和 j 的值分别是（ ）。 【出自：2015年全国统考408，提示：这里i、j的取值范围是从0开始的】
A、i=1,j=0
B、i=5,j=0
C、i=5,j=2
D、i=6,j=2
E、i=6,j=0
第4题
设问题规模为n时，某递归算法的时间复杂度记为T(n)，已知T(1)=1, T(n)=2T(n/2)+n/2，用O表示的时间复杂度为( )
A、O(logn)
B、O(n)
C、O(nlogn)
D、O(n2logn)
第6题
设某算法的计算时间表示为递推关系式T(n) = T(n - 1) + n（n为正整数）及T(0) = 1，则 该算法的时间复杂度为（ ）。
A、O(log n)
B、O(n log n)
C、O(n)
D、O(n2)
第8题
在某个算法时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（），若问题的规模增加了16倍，则运行时间增加（）倍。
A.Θ(n) B.Θ(nlgn) C.Θ(n2) D.Θ(n2lgn) A.16 B.64 C.256 D.1024
第10题
设字符串t和p的长度分别为m和n.t的后缀数组和最长公共前缀数组分别为sa和lcp.请说明如何利用t的后缀数组和最长公共前缀数组搜索给定字符串p在t中出现的所有位置.要求算法在最坏情况下的时间复杂性为O(m+logn).
