全部科目 > 软件设计师 >
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




 
 
相关试题     计算机软件知识 

  第26题    2012年上半年  
假设一台按字节编址的16位计算机系统，采用虚拟页式存储管理方案，页面的大小为2K，且系统中没有使用快表（或联想存储器)。某用户程序如图a所示，该程序的页面变..

  第56题    2019年下半年  
事务的(56)是指，当某个事务提交(COMMIT)后，对数据库的更新操作可能还停留在服务器的磁盘缓冲区而未写入磁盘时，即使系统发生故障，事务的执行结果仍不会丢失。..

  第60题    2019年下半年  
对于如下所示的有向图，其邻接矩阵是一个(60)的矩阵。采用邻接链表存储时，顶点1的表结点个数为2，顶点5的表结点个数为0，顶点2和3的表结点个数分别为(61)。

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



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

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