免费智能真题库 > 历年试卷 > 软件设计师 > 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
 
 
 

  相关试题:串          更多>  
 
  第62题    2009年下半年  
   56%
字符串采用链表存储方式时,每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串,在串比较、求子串、串连..
  第57题    2017年上半年  
   32%
以下关于字符串的叙述中,正确的是( )。
  第57题    2017年下半年  
   60%
设S是一个长度为n的非空字符串,其中的字符各不相同,则其互异的非平凡子串(非空且不同于S本身)个数为( )。
   知识点讲解    
   · 串的模式匹配
 
       串的模式匹配
        子串的定位操作通常称为串的模式匹配,它是各种串处理系统中最重要的运算之一。子串也称为模式串。
        1)朴素的模式匹配算法
        朴素的模式匹配算法也称为布鲁特一福斯算法,其基本思想是:从主串的第一个字符起与模式串的第一个字符比较,若相等则继续逐个字符进行后续的比较,否则从主串的第二个字符起与模式串的第一个字符重新比较,直至模式串中的每个字符依次和主串中的一个连续的字符序列相等,则称匹配成功,否则称匹配失败。
        该算法在最好情况下匹配算法的时间复杂度为O(n+m),而在最坏情况下的时间复杂度为O(n×m)。
        2)改进的模式匹配算法
        改进的模式匹配算法又称为KMP算法,其改进之处在于:每当匹配过程中出现相比较的字符不相等时,不需要回溯主串的指针,而是利用已经得到的"部分匹配"的结果,将模式串向后"滑动"尽可能远的距离,再继续进行比较。
        此算法的时间复杂度为O(n+m)。
   题号导航      2012年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第57题    在手机中做本题