设主串的长度为n，子串的长度为m，BF算法的时间复杂度为O（m+n)

题目

设主串的长度为n，子串的长度为m，BF算法的时间复杂度为O（m+n)

相似考题

1.设串的长度为n,则它的子串个数为()。A、nB、n(n+1)C、n(n+1)/2D、n(n+1)/2+1

2.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()A、O(m+n)B、O(n)C、O(m)D、O(1)

3.●设A和B是两个单链表，其表中元素有序递增。请分析算法的时间复杂度。其时间复杂度为 (40) 。(40) A．O(m+n-1)B．(m+n+1)C．O(m+n)D．不确定

4.设串S的长度为n,则S的子串个数为n(n＋1)／2。()此题为判断题(对，错)。

更多“设主串的长度为n，子串的长度为m，BF算法的时间复杂度为O（m+n)”相关问题

  • 第1题：

    对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。串＜1，0，0，1，0，1，0，1，＞和＜0，1，0，1，1，0，1，1，＞的最长公共子序列的长度为(58)。

    A．分治

    B．贪心

    C．动态规划

    D．分支一限界


    正确答案：C
    解析：本题考查的是动态规划算法策略的典型应用。LCS问题是利用动态规划策略解决的经典问题之一，利用动态规划求解该问题时可以通过查表得到已经计算出的子串的最长公共子序列，从而避免重复计算。利用动态规划算法可以得到题目中两个串的最长公共子序列长度为6，如“101011”。

  • 第2题：

    设序列长度为n，在最坏情况下，时间复杂度为O(log2n)的算法是()。

    A.二分法查找

    B.顺序查找

    C.分块查找

    D.哈希查找


    正确答案：A

  • 第3题：

    设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 ( )

    A．m

    B．n-m

    C．n-m+1

    D．n


    正确答案：C

  • 第4题：

    对于求取两个长度为n的字符串的最长公共子序列问题，利用(41)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。

    A．贪心

    B．分治

    C．分支-限界

    D．动态规划


    正确答案：D
    解析：对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，是利用动态规划策略解决的经典问题之一。利用动态规划策略求解该问题时可以通过查表得到已经计算出的子串的最长公共子序列，从而避免重复计算。例如，利用动态规划算法可以得到串1，0,0,1，0，1，0，1＞和0，1，0，1，1，0，1，1＞的最长公共子序列的长度为6，如“101011”。

  • 第5题：

    设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为_______。

    A.O(1)

    B.O(log2n)

    C.O(n)

    D.O(n2)


    正确答案：C

  • 第6题：

    阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
    [说明]
    下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度L及其在各字符串中的起始位置(L=0时不存在公共字串)。例如，字符串"The light is not bright tonight"与"Tonight the light is not bright"的最长公共子串为"he light is not bright"，长度为22，起始位置分别为2和10。
    设A[1:M]表示由M个字符A[1]，A[2]，…，A[M]依次组成的字符串；B[1:N]表示由N个字符B[1]，B[2]，…，B[N]依次组成的字符串，M≥N≥1。
    本流程图采用的算法是：从最大可能的公共子串长度值开始逐步递减，在A、B字符串中查找是否存在长度为L的公共子串，即在A、B字符串中分别顺序取出长度为L的子串后，调用过程判断两个长度为L的指定字符串是否完全相同(该过程的流程略)。
    [流程图]


    答案：
    解析：
    N或rnin(M，N)
    M-L+1
    N-L+1
    L-1
    L，I，J

    【解析】

    本题考查对算法流程图的理解和绘制能力。这是程序员必须具有的技能。
    本题的算法可用来检查某论文是否有大段抄袭了另一论文。"The light is not bright tonight"是著名的英语绕口令，它与"Tonight the light is not bright"大同小异。
    由于字符串A和B的长度分别为M和N，而且M≥N≥1，所以它们的公共子串长度L必然小于或等于N。题中采用的算法是，从最大可能的公共子串长度值L开始逐步递减，在A、B字符串中查找是否存在长度为L的公共子串。因此，初始时，应将min(M，N)送L，或直接将N送L。(1)处应填写N或min(M，N)，或其他等价形式。
    对每个可能的L值，为查看A、B串中是否存在长度为L的公共子串，显然需要执行双重循环。A串中，长度为L的子串起始下标可以从l开始直到M-L+1(可以用实例来检查其正确性)；B串中，长度为L的子串起始下标可以从1开始直到N-L+1。因此双重循环的始值和终值就可以这样确定，即(2)处应填M-L+1，或等价形式；(3)处应填N-L+1或等价形式(注意循环的终值应是最右端子串的下标起始值)。
    A串中从下标I开始长度为L的子串可以描述为A[I:I+L-1]；B串中从下标J开始长度为L的子串可以描述为A[J:J+L-1]。因此，双重循环体内，需要比较这两个子串(题中采用调用专门的函数过程或子程序来实现)。
    如果这两个子串比较的结果相同，那么就已经发现了A、B串中最大长度为L的公共子串，此时，应该输出公共子串的长度值L、在A串中的起始下标I、在B串中的起始下标J。因此，(5)处应填L，I，J(可不计顺序)。
    如果这两个子串比较的结果不匹配，那么就需要继续执行循环。如果直到循环结束仍然没有发现匹配子串时，就需要将L减少1((4)处填L-1或其等价形式)。只要L非0，则还可以继续对新的L值执行双重循环。如果直到L=0，仍没有发现子串匹配，则表示A、B两串没有公共子串。

  • 第7题：

    将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。

    • A、O（1）
    • B、O（n）
    • C、O（m）
    • D、O（m+n）

    正确答案:C

  • 第8题：

    已知序列X={x1，x2，…，xm}，序列Y={y1，y2，…，yn}，使用动态规划算法求解序列X和Y的最长公共子序列，其最坏时间复杂度为（）。

    • A、O（m*n）
    • B、O（m+n）
    • C、O（m*2n）
    • D、O（n*2m）

    正确答案:A

  • 第9题：

    两个字符串S1和S2的长度分别为m和n，求这两个字符串最大共同子串的时间复杂度为T（m，n），这最优的时间复杂度为（）。


    正确答案:O(m*n)

  • 第10题：

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

    • A、O（m）
    • B、O（n）
    • C、O（m*n）
    • D、O（nlog2m）

    正确答案:A

  • 第11题：

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

    O（m）

    B

    O（n）

    C

    O（m*n）

    D

    O（nlog2m）


    正确答案： C
    解析： KMP算法时间复杂度为O(m+n)，空间复杂度是O(m).因为KMP算法设计到next数组的存储，且next数组是基于模式串长度计算的。
    BF算法（普通匹配算法）时间复杂度为O(m*n)；空间复杂度为O(1).

  • 第12题：

    填空题
    两个字符串S1和S2的长度分别为m和n，求这两个字符串最大共同子串的时间复杂度为T（m，n），这最优的时间复杂度为（）。

    正确答案： O(m*n)
    解析： 暂无解析

  • 第13题：

    设主串长为n，模式串长为m(m≤n)，则在匹配失败的情况下，朴素匹配算法进行的无效位移次数为(30)。

    A．m

    B．n-m

    C．n-m+1

    D．n


    正确答案：C
    解析：本题考查字符串的匹配内容。字符串是由某字符集上的字符所组成的任何有限字符序列。字符串的匹配实际上就是在一个字符串中查找另一个字符串，如果查找到则说明匹配成功。在一个字符串中查找另一个字符串时，是从主串的第一个字符开始的，用其第一个字符与模式串中的第一个字符比较，看是否相等，如果不等则主串往后移动一位，如果查找不到，那么只需要把主串移动到n-m+1位置即可，因为后面就算再出现能查找到的情况那也没有模式串的长度了，肯定不能完全查找出模式串。那么在匹配过程中，进行的无效位移次数为n-m+1次。

  • 第14题：

    将长度为n的单链表链接到长度为m的单链表之后的算法的时间复杂度是()。

    A.O(1)

    B.O(n)

    C.O(m)

    D.O(m+n)


    参考答案：C

  • 第15题：

    设A和B是两个单链表，其表中元素有序递增。请分析算法的时间复杂度。其时间复杂度为(40)。

    A．O(re+n-1)

    B．(m+n+1)

    C．O(m+n)

    D．不确定


    正确答案：C
    解析：设A表和B表的长度分别为m和n，则该算法的时间复杂度为O(m+n)。

  • 第16题：

    若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。

    A．O(1)

    B．O(n)

    C．O(n2)

    D．0(n3)


    正确答案：C
    解析：在主串中可能存在多个模式串“部分匹配”的子串，因而引起数次回溯，若除了最后一次匹配，其他比较每次都需要回溯，则循环次数的数量级为n2。

  • 第17题：

    对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用(24)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。串 ＜1，0，0，1，O，1，0，1＞和＜0，1，0，1，1,0,1，1＞的最长公共子序列的长度为(25)。

    A．分治

    B．贪心

    C．动态规划

    D．分支—限界


    正确答案：C

  • 第18题：

    将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为()。

    A.O(n)
    B.0(1)
    C.O(m)
    D.O(m+n)

    答案：C
    解析：
    要将长度为n的单链表接在长度为m的单链表之后，必须从单链表的头结点沿链找到长度为m的单链表的最后一个结点，所以时间复杂度为O(m)。

  • 第19题：

    下面程序的时间复杂度为（）。 for（i=0；i

    • A、O（m2）
    • B、O（n2）
    • C、O（m×n）
    • D、O（m+n）

    正确答案:C

  • 第20题：

    下面程序的时间复杂度为（）。 for（i=0；i

    • A、O（m×n×t）
    • B、O（m+n+t）
    • C、O（m+n×t）
    • D、O（m×t+n）

    正确答案:A

  • 第21题：

    长度为n的串s1与长度为2n的串s2的比较运算的时间复杂度是（）。


    正确答案:O（n）

  • 第22题：

    单选题
    将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。
    A

    O（1）

    B

    O（n）

    C

    O（m）

    D

    O（m+n）


    正确答案： D
    解析： 暂无解析

  • 第23题：

    单选题
    设串的长度为n，则它的子串个数为（）。
    A

    n

    B

    n（n+1）

    C

    n（n+1）/2

    D

    n（n+1）/2+1


    正确答案： C
    解析： 暂无解析

  • 第24题：

    填空题
    长度为n的串s1与长度为2n的串s2的比较运算的时间复杂度是（）。

    正确答案： O（n）
    解析： 暂无解析

相关内容