工学
填空题若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为（）。
题目
相似问题和答案
第1题：
● 若字符串s 的长度为 n（n >1）且其中的字符互不相同，则 s 的长度为 2 的子串有 （35） 个。
（35）
A. n
B. n-1
C. n-2
D. 2
第2题：
阅读以下说明和流程图，填补流程图中的空缺(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 解析：本题采用的是最简单的字符子串查找算法。
在串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)。
在设计流程图时，主要的难点是确定循环的边界(何时开始，何时结束)。当难以确定边界值变量的正确性时，可以用具体的数值之例来验证。这是程序员应具备的基本素质。
第3题：
设主串长为n，模式串长为m(m≤n)，则在匹配失败的情况下，朴素匹配算法进行的无效位移次数为(30)。
A．m
B．n-m
C．n-m+1
D．n
解析：本题考查字符串的匹配内容。字符串是由某字符集上的字符所组成的任何有限字符序列。字符串的匹配实际上就是在一个字符串中查找另一个字符串，如果查找到则说明匹配成功。在一个字符串中查找另一个字符串时，是从主串的第一个字符开始的，用其第一个字符与模式串中的第一个字符比较，看是否相等，如果不等则主串往后移动一位，如果查找不到，那么只需要把主串移动到n-m+1位置即可，因为后面就算再出现能查找到的情况那也没有模式串的长度了，肯定不能完全查找出模式串。那么在匹配过程中，进行的无效位移次数为n-m+1次。
第4题：
设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 ( )
A．m
B．n-m
C．n-m+1
D．n
第5题：
若字符串s的长度为n(n＞1)且其中的字符互不相同，则s的长度为2的子串有______个。
A．n
B．n-1
C．n-2
D．2
A．
B．
C．
D．
第6题：
设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。
A、求子串
B、联接
C、模式匹配
D、求串长
第7题：
A、连接
B、求串长
C、串比较
D、子串定位
E、串复制
第8题：
●在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为n和m（且n远大于m），且恰好在主串末尾的m个字符处匹配成功，则在上述的模式匹配过程中,字符的比较次数最多为(57)。
(57) A. n*m
B. (n-m+1)*m
C. (n-m-1)*m
D. (n-m)*n
第9题：
以下函数fun的功能是返回str所指字符串中以形参c中字符开头的后续字符串的首地址，例如，str所指字符串为Hello!，c中的字符为e，则函数返回字符串ello!的首地址。若str所指字符串为空或不包含c中的字符，则函数返回NULL，请填空。char *fun(char *str,char c){ int n=0; char *p=str; if(p!=NULL) while(p[n]!=c&&p[n]!=’\0’) n++; if(p[n]==’\0’) return NULL; return();}
在本题中，函数fun的功能是返回str所指字符串中以形参c中字符开头的后续字符串的首地址。
在本题的程序中，fun函数带有两个形参，其中一个是指针str，它指向字符串的首地址，另一个是字符变量c。程序首先定义了一个整型变量n，从程序中可知，它是字符串str中参数c相对于首地址的偏移量，然后定义了一个指针变量p，指向字符串str的首地址，然后执行条件语句，如果字符串不为空，则执行循环语句，循环结束的条件是要么字符串结束，要么找到形参c中对应的字符。根据循环结束的条件我们可以判断，其非死循环，循环结束后，从程序中可以看出，判断循环结束的原因是否因为字符串结束而结束的，如果是，说明没找到形参c中对应的字符，返回NULL。
如果不是，则说明是因为找到了形参c中对应的字符而结束循环的。根据题目要求，需要返回以形参c中字符开头的后续字符串的首地址，而这时以形参c中字符开头的后续字符串的首地址为p+n。
第10题：
阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入对应栏内。
[说明]
下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。
设这篇文章由字符A(0)，…，A(n-1)依次组成，指定关键词由字符B(0)，…，B(m-1)依次组成，其中，n＞m≥1。注意，关键词的各次出现不允许有交叉重叠。例如，在“aaaa”中只出现两次“aa”。
该流程图采用的算法是：在字符串A中，从左到右寻找与字符串B相匹配的并且没有交叉重叠的所有子串。流程图中，i为字符串A中当前正在进行比较的动态予串首字符的下标，j为字符串B的下标，k为指定关键词出现的次数。
[流程图]
0-k i+j i+m i+1 i 解析：本题考查用流程图描述算法的能力。
在文章中查找某关键词出现的次数是经常碰的问题。例如，为了给文章建立搜索关键词，确定近期的流行语，迅速定位文章的某个待修改的段落，判断文章的用词风格，甚至判断后半本书是否与前半本书是同一作者所写(用词风格是否一致)等，都采用了这种方法。
流程图最终输出的计算结果K就是文章字符串A中出现关键词字符串B的次数。显然，流程图开始时应将K赋值0，以后每找到一处出现该关键词，就执行增1操作K=K+1。
因此(1)处应填0→K。
字符串A和B的下标都是从0开始的。所以在流程图执行的开始处，需要给它们赋值0。接下来执行的第一个小循环就是判断A(i)，A(i+1)，…，A(i+j-1)是否完全等于B(0)，B(1)，…，B(m-1)，其循环变量j=0，1，…，m-1。只要发现其中对应的字符有一个不相等时，该小循环就结束，不必再继续执行该循环。因此，该循环中继续执行的判断条件应该是A(i+j)=B(j)且jm。只要遇到A(i+j)≠B(j)或者j=m(关键词各字符都己判断过)就不再继续执行该循环了。因此流程图的(2)处应填州i+j。
许多考生在(2)处填i，当j增1变化后，仍然使用A(i)进行比较就不对了。因此，在检查循环程序段时应多走查一次循环。
如果(2)处整体的判断条件不成立，则该判断关键词的小循环结束。此时可能有两种情况。一是在j=0，1，…，m-1时全都成立A(i+j)=B(j)(找到了一处关键词)，直到j=m时才结束小循环；二是在jm时就发现了字符不等的情况，这说明此处并不出现关键词。因此流程图中用jm来区分找到与没有找到关键词的两种情况。
对于j=m，已找到一处关键词的情况，显然应该执行k=k+1，对关键词出现次数的变量k进行增1计算。同时，为了继续进行以后的判断，应将字符串A的下标i右移m(这是因为题中假设关键词的出现不允许重叠)。因此(3)处应填写i+m，表示应该从已出现的关键词后面开始再继续进行判断。由于此时的j=m，书写i+j的答案也是正确的，但这不是程序员的好习惯，因为这不符合逻辑思维的顺势，在程序不断修改的过程中容易出错。不少考生在(3)处填写i+1，这意味着下次判断关键词将从A(i+1)开始，这就使关键词的出现有可能发生部分重叠的现象。
流程图中，对于jm的情况，表示刚才判断关键词时并非各个字符都完全相同，也就是说，刚才的判断结论是此处并没有出现关键词。即A(i)开始的子串并不是关键词。因此，下次判断关键词应该以A(i+1)开始，即(4)处应填i+1。
在下次判断关键词之前还应该判断是否全文已经判断完。最后一次小循环判断应该是对A(n-m)，A(n-m+1)，…，A(n-1)的判断。下标n-m来自从n-1倒数m个数。可以先试验写出A(n-m)，A(n-m+1)，…，A(n-1)，再判断其个数是否为m。经检查，个数为(n-1)-(n-m)+1=m个，所以这是正确的。也可以用例子来检查次数是否正确。检查次数是程序员的基本功，数目的计算很容易少一个或多一个。
既然最后一次判断关键词应该是对A(n-m)，A(n-m+1)，…，A(n-1)的判断，即对i=n-m进行的小循环判断，所以当i＞n-m时就应该停止大循环，停止再查找关键词了。