全部科目 > 软件设计师 >
2012年下半年 上午试卷 综合知识
第 57 题
知识点 串的模式匹配  
关键词 模式匹配   匹配算法   子串   字符串   算法  
章/节 计算机软件知识  
 
 
在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特一福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为n和m (且n远大于m),且恰好在主串末尾的m个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为（57)。
 
  A.  n*m
 
  B.  (n-m+1)*m
 
  C.  (n-m-1)*m
 
  D.  (n-m)*n




 
 
相关试题     计算机软件知识 

  第53题    2009年上半年  
假设员工关系EMP (员工号，姓名，部门，部门电话，部门负责人，家庭住址，家庭成员，成员关系）如下表所示。如果一个部门可以有多名员工，一个员工可以有多个家庭..

  第49题    2013年下半年  
对高级语言源程序进行编译的过程中，有限自动机(NFA或DFA)是进行(49)的适当工具。

  第48题    2013年上半年  
以下关于语言L={anbn|n>=1}的叙述中，正确的是（48）。

 
知识点讲解
· 串的模式匹配
 
        串的模式匹配
        子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。
        1）朴素的模式匹配算法
        朴素的模式匹配算法也称为布鲁特一福斯算法，其基本思想是：从主串的第一个字符起与模式串的第一个字符比较，若相等则继续逐个字符进行后续的比较，否则从主串的第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和主串中的一个连续的字符序列相等，则称匹配成功，否则称匹配失败。
        该算法在最好情况下匹配算法的时间复杂度为O(n+m)，而在最坏情况下的时间复杂度为O(n×m)。
        2）改进的模式匹配算法
        改进的模式匹配算法又称为KMP算法，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的指针，而是利用已经得到的"部分匹配"的结果，将模式串向后"滑动"尽可能远的距离，再继续进行比较。
        此算法的时间复杂度为O(n+m)。



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2026 All Rights Reserved
软考在线版权所有