模式匹配的改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯-普拉特操作简称（）。A、KMP算法B、Prime算法C、克鲁斯卡尔算法D、迪杰斯特拉算法

题目

模式匹配的改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯-普拉特操作简称（）。

  • A、KMP算法
  • B、Prime算法
  • C、克鲁斯卡尔算法
  • D、迪杰斯特拉算法
相似考题

1.●在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为n和m（且n远大于m），且恰好在主串末尾的m个字符处匹配成功，则在上述的模式匹配过程中,字符的比较次数最多为(57)。(57) A. n*mB. (n-m+1)*mC. (n-m-1)*mD. (n-m)*n

2.设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa” ① 计算模式p的naxtval函数值; ② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。

3.阅读以下算法说明和C程序，根据要求回答问题1至问题2。[说明][算法4-1]的功能是：用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如图4-18所示。在[算法4-1]中，stack为一整数栈。算法中各函数的说明如表4-16所示。[算法4-1] 将栈stack置空，置EOF为false为了识别更多种类的括号，对[算法4-1]加以改进后得到[算法4-2]。[算法4-2]能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(charch)的参数及其对应的返回值如表4-17所示。[算法4-2][问题1]请将[算法4-1]和[算法4-2]中，(1)～(7)空缺处的内容补充完整。[问题2]请从以下选项中选择相应的判断逻辑填补[算法4-2]中的“判断条件1”至“判断条件3”。注意，若“判断条件2”的逻辑判断结果为假，就无需对“判断条件3”进行判断。判断条件1： (8)判断条件2： (9)判断条件3： (10)[供选择的答案]A．栈顶元素表示的是与当前字符匹配的左括号B．栈顶元素表示的是与当前字符匹配的右括号C．字符是左括号 D．字符是右括号 E．栈不空 F．栈空G．字符是括号

4.设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。A、求子串B、联接C、模式匹配D、求串长

参考答案和解析
正确答案:A
更多“模式匹配的改进算法是D.E.Knuth与V.R.Pratt和J.”相关问题

  • 第1题：

    当运用改进的模式匹配算法时，模式串P='ABAABCAC'的next函数值序列为(41)。

    A．1222312

    B．1122312

    C．1122212

    D．122312


    正确答案：B
    解析：改进的模式匹配算法的不同之处在于，每当匹配失效时，不需要回溯主串的指针，而是复用已经得到的“部分匹配”的结果，将模式串向后“滑动”尽可能远的距离，再继续进行比较。算法执行时就依据模式串的next函数值实现子串的滑动。next函数定义如下：依据此函数定义即可算得next函数值序列为01122312。

  • 第2题：

    ● 在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为n和m（且n远大于m），且恰好在主串末尾的m个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为（57）。 A.n*m B.（n-m+1）*m C.（n-m-1）*m D.（n-m）*n


    正确答案：B
    试题57分析本题主要考查字符串的匹配。在本题的描述中，告诉我们是在主串末尾的m个字符处匹配成功，那么在这之前，从左到右依次匹配了n-m次，且都失败了，最坏的情况，就是每次匹配都是匹配到最后一个字符不符合，因此每次匹配的比较次数就是子串的长度，即m。而匹配成功时，一共也比较了m次。所以字符的比较次数最多为（n-m+1）*m次。参考答案（57）B

  • 第3题：

    KMP算法的特点是在模式匹配时指示主串的指针不会回溯。


    正确答案:正确

  • 第4题：

    case语句将word和模式从头至尾进行比较，当遇到第一个匹配模式时，执行与该模式相应的命令。每行匹配所对应的命令的结尾符号是（）

    • A、，
    • B、；
    • C、；；
    • D、。

    正确答案:C

  • 第5题：

    ACL规则的匹配顺序包括两种：顺序匹配和自动匹配。由于自动匹配采用的是“深度优先”的算法，可以更加有效的进行匹配，所有系统默认的匹配顺序是自动匹配。（）


    正确答案:错误

  • 第6题：

    KMP模式匹配算法是由（）同时发现的，因此而得名。

    • A、莫里斯
    • B、克努特
    • C、普拉特
    • D、克鲁伊特

    正确答案:A,B,C

  • 第7题：

    以下哪一个模式是对算法的封装，它把算法的责任和算法本身分割开，委派给不同的对象管理（）

    • A、策略模式
    • B、模版方法模式
    • C、解释器模式
    • D、迭代器模式

    正确答案:A

  • 第8题：

    判断题
    朴素模式匹配算法，算法运行时间为O（m*n）。
    A

    对

    B

    错


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

  • 第9题：

    单选题
    下列分区管理的分配算法中，分配与释放时间性能最好的是（）
    A

    最先匹配法

    B

    最佳匹配法

    C

    下次匹配法

    D

    最坏匹配法


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

  • 第10题：

    单选题
    case语句将word和模式从头至尾进行比较，当遇到第一个匹配模式时，执行与该模式相应的命令。每行匹配所对应的命令的结尾符号是（）
    A

    ，

    B

    ；

    C

    ；；

    D

    。


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

  • 第11题：

    单选题
    以下各种影像匹配方法中，可以考虑辐射畸变和几何变形的算法是（）
    A

    协方差函数测度匹配算法

    B

    相关系数测度匹配算法

    C

    铅垂线轨迹法

    D

    最小二乘法影像匹配


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

  • 第12题：

    单选题
    KMP模式匹配算法的改进之处是（）。
    A

    主串指针不需要回溯

    B

    模式串的指针来回移动

    C

    主串的指针也会回到之前比较过的字符

    D

    时间复杂度可以达到O（nm）


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

  • 第13题：

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

    A．m

    B．n-m

    C．n-m+1

    D．n


    正确答案：C

  • 第14题：

    KMP算法的特点是在模式匹配时指示主串的指针()。

    A.不会变大
    B.不会变小
    C.都有可能
    D.无法判断

    答案：B
    解析：
    在KMP算法中，模式匹配时主串不会回溯，所以主串的指针不会变小。

  • 第15题：

    KMP模式匹配算法的改进之处是（）。

    • A、主串指针不需要回溯
    • B、模式串的指针来回移动
    • C、主串的指针也会回到之前比较过的字符
    • D、时间复杂度可以达到O（nm）

    正确答案:A

  • 第16题：

    将word和模式从头至尾进行比较，当遇到第一个匹配模式时，执行与该模式相应的命令。每行匹配所对应的命令均以双重分号“；；”结尾，完成这一功能的语句是（）

    • A、case
    • B、switch
    • C、shell
    • D、for

    正确答案:A

  • 第17题：

    下列分区管理的分配算法中，分配与释放时间性能最好的是（）

    • A、最先匹配法
    • B、最佳匹配法
    • C、下次匹配法
    • D、最坏匹配法

    正确答案:A

  • 第18题：

    朴素模式匹配算法，算法运行时间为O（m*n）。


    正确答案:正确

  • 第19题：

    以下参数中，与速率匹配无关的是（）

    • A、打孔
    • B、重复
    • C、TTI
    • D、RM算法

    正确答案:C

  • 第20题：

    判断题
    ACL规则的匹配顺序包括两种：顺序匹配和自动匹配。由于自动匹配采用的是“深度优先”的算法，可以更加有效的进行匹配，所有系统默认的匹配顺序是自动匹配。（）
    A

    对

    B

    错


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

  • 第21题：

    多选题
    KMP模式匹配算法是由（）同时发现的，因此而得名。
    A

    莫里斯

    B

    克努特

    C

    普拉特

    D

    克鲁伊特


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

  • 第22题：

    单选题
    以下参数中，与速率匹配无关的是（）
    A

    打孔

    B

    重复

    C

    TTI

    D

    RM算法


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

  • 第23题：

    判断题
    KMP算法的特点是在模式匹配时指示主串的指针不会回溯。
    A

    对

    B

    错


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

相关内容