若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为（）。
题目
若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为（）。
相似考题
参考答案和解析
更多“若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下”相关问题
-
第1题：
●在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为n和m（且n远大于m），且恰好在主串末尾的m个字符处匹配成功，则在上述的模式匹配过程中,字符的比较次数最多为(57)。
(57) A. n*m
B. (n-m+1)*m
C. (n-m-1)*m
D. (n-m)*n
正确答案：B
-
第2题：
设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。
A、求子串
B、联接
C、模式匹配
D、求串长
正确答案:C
-
第3题：
串的基本操作包括()A、连接
B、求串长
C、串比较
D、子串定位
E、串复制
参考答案：ABCDE
-
第4题：
设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 ( )
A．m
B．n-m
C．n-m+1
D．n
正确答案：C
-
第5题：
● 在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为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 -
第6题：
给定程序中，函数fun的功能是：在形参ss所指字符串数组中，查找含有形参substr所指子串的所有字符串并输出，若没找到则输出相应信息。ss所指字符串数组中共有N个字符串，且串长小于M。程序中库函数strstr(s1，s2)的功能是在s1串中查找s2子串，若没有，函数值为0，若有，为非0。
请在程序的下划线处填入正确的内容并把下划线删除，使程序得出正确的结果。
注意：源程序存放在考生文件夹下的BLANKl．C中。
不得增行或删行，也不得更改程序的结构！
正确答案：(1)N (2)substr (3)0
(1)N (2)substr (3)0 解析：本题中函数fun的功能是在形参ss所指字符串数组中，查找含有形参substr所指子串的所有字符串并输出，若没找到则输出相应信息。
在fun函数中，利用循环逐个查找ss所指字符串数组中的每一个字符串，并判断是否含有substr所指的子串，有则输出。 -
第7题：
在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为“abaac”，则其next函数值为 (60) 。
A.01234
B.01122
C.01211
D.01111
正确答案：B
本题考查字符串的模式匹配运算知识。KMP是进行字符串模式匹配运算效率较高的算法。根据对next函数的定义，模式串前两个字符的next值为0、1。对于第3个字符“a”，其在模式串中的前缀为“ab”从该子串找不出前缀和后缀相同的部分，因此，根据定义，该位置字符的next值为1。对于第4个字符“a”，其在模式串中的前缀为“aba”，该子串只有长度为l的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。对于第5个字符“a”，其在模式串中的前缀为“abaa”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。综上可得，模式串“abaac”的next函数值为01122。 -
第8题：
阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
[说明]
下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度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两串没有公共子串。 -
第9题：
子串定位函数的时问复杂度在最坏情况下为0（n×m）因此子串定位函数没有实际使用的价值。
正确答案:错误 -
第10题：
在易发生严重覆冰地区，宜增加绝缘子串长或采用（）串，（）串。
正确答案:V型；八字 -
第11题：
单选题设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。AO（m）
BO（n）
CO（m*n）
DO（nlog2m）
正确答案： C解析： KMP算法时间复杂度为O(m+n)，空间复杂度是O(m).因为KMP算法设计到next数组的存储，且next数组是基于模式串长度计算的。
BF算法（普通匹配算法）时间复杂度为O(m*n)；空间复杂度为O(1). -
第12题：
单选题数据结构里，设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。A求子串
B联接
C匹配
D求串长
正确答案： C解析： 暂无解析 -
第13题：
● 若字符串s 的长度为 n（n >1）且其中的字符互不相同，则 s 的长度为 2 的子串有 （35） 个。
（35）
A. n
B. n-1
C. n-2
D. 2
正确答案：B
-
第14题：
阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入对应栏内。
【说明】
下面流程图的功能是：在已知字符串A中查找特定字符串B，如果存在，则输出B串首字符在A串中的位置，否则输出-1。设串A由n个字符A(0)，A(1)，…，A(n-1)组成，串B由m个字符B(0)，B(1)，…，B(m-1)组成，其中n≥m＞0。在串A中查找串 B的基本算法如下：从串A的首字符A(0)开始，取子串A(0)A(1)…A(m-1)与串B比较；若不同，则再取子串A(1)A(2)…A(m)与串B比较，依次类推。
例如，字符串“CABBRFFD”中存在字符子串“BRF”(输出3)，不存在字符子串“RFD”(输出-1)。
在流程图中，i用于访问串A中的字符(i=0，1，…，n-1)，j用于访问串B中的字符(j=0，1，…，m-1)。在比较A(i)A(i/1)…A(i+m-1)与B(0)B(1)…B(m-1)时，需要对 A(i)与B(0)、A(i+1)与B(1)、…、A(i+j)与B(j)等逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。
【流程图】
正确答案：(1) j+1 (2) i+1 (3) 0 (4) i (5) -1
(1) j+1 (2) i+1 (3) 0 (4) i (5) -1 解析：本题采用的是最简单的字符子串查找算法。
在串A中查找是否含有串B，通常是在串A中从左到右取逐个子串与串B进行比较。在比较子串时，需要从左到右逐个字符进行比较。
题中已设串A的长度为n，存储数组为A，动态指针标记为i；串B的长度为m，存储数组为B，动态指针标记为j。
如果用伪代码来描述这种算法的核心思想，则可以用以下的两重循环来说明。
外循环为：
Fori=0ton-mdo
A(i)A(i+1)...A(i+m-1)～B(0)B(1)...B(m-1)
要实现上述比较，可以采用内循环：
Forj=0tom-1do
A(i+j)～B(j)
将这两重循环合并在一起就是：
Fori = 0ton-1do
Forj = 0tom-1do
A(i+j)～B(j)
这两重循环都有一个特点：若发现比较的结果不相同时，就立即退出循环。因此，本题中的流程图可以间接使用循环概念。
初始时，i与j都赋值0，做比较A(i+j)～B(j)。
若发现相等，则继续内循环(走图的左侧)，j应该增1，继续比较，直到j=m为止，表示找到了子串(应输出子串的起始位置i)；若发现不等，则退出内循环，继续开始外循环(走图的右侧)，j应恢复为0，i应增1，继续比较，直到i＞n-m为止，表示不存在这样的子串(输出-1)。
在设计流程图时，主要的难点是确定循环的边界(何时开始，何时结束)。当难以确定边界值变量的正确性时，可以用具体的数值之例来验证。这是程序员应具备的基本素质。 -
第15题：
若字符串s的长度为n(n＞1)且其中的字符互不相同，则s的长度为2的子串有______个。
A．n
B．n-1
C．n-2
D．2
A．
B．
C．
D．
正确答案：B
-
第16题：
对串s和串t，为串t在串s中定位的运算称为( )。
A．判等
B．模式匹配
C．求串长
D．求子串
正确答案：B
解析：子串的定位操作称为串的模式匹配。 -
第17题：
若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。
A．O(1)
B．O(n)
C．O(n2)
D．0(n3)
正确答案：C
解析：在主串中可能存在多个模式串“部分匹配”的子串，因而引起数次回溯，若除了最后一次匹配，其他比较每次都需要回溯，则循环次数的数量级为n2。 -
第18题：
以下关于字符串的叙述中，正确的是 （ ）。
A.字符串属于线性的数据结构B.长度为0字符串称为空白串C.串的模式匹配算法用于求出给定串的所有子串D.两个字符串比较时，较长的串比较短的串大
正确答案：A
-
第19题：
若串s一”MathTypes”，则其子串的数目是【3】
正确答案：
【3】46 -
第20题：
在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为"abaac"，则其next函数值为 （ ） 。
A.01234
B.01122
C.01211
D.01111答案：B解析：根据公式依次推导即可。 -
第21题：
数据结构里，设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。
- A、求子串
- B、联接
- C、匹配
- D、求串长
正确答案:C -
第22题：
填空题若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为（）。正确答案： (n-m+1)*m解析： 暂无解析 -
第23题：
判断题子串定位函数的时问复杂度在最坏情况下为0（n×m）因此子串定位函数没有实际使用的价值。A对
B错
正确答案： 错解析： 暂无解析