计算机类
判断题子串“ABC”在主串“AABCABCD”中的位置为2。( )A 对B 错
题目
判断题
子串“ABC”在主串“AABCABCD”中的位置为2。( )
A
对
B
错
参考答案和解析
正确答案：
错
解析：
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案
第1题：
设主串为“ABcCDABcdEFaBc”,以下模式串能与主串成功匹配的是()。
A.BCd
B.Bcd
C.Abc
D.ABC
参考答案：B
第2题：
阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
[说明]
下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度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的指定字符串是否完全相同(该过程的流程略)。
[流程图]
[说明]
下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度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两串没有公共子串。
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两串没有公共子串。
第3题：
设有两个串T和P,求P在T中首次出现的位置的串运算称作()。
A、联接
B、求子串
C、字符定位
D、子串定位
正确答案:D
第4题：
如果t中存在等于p的子串，就指出该子串在t中的位置，称为匹配成功；否则称为匹配失败。
正确答案:正确
第5题：
在使用string类的find成员函数来检索主串中是否含有指定的子串时，若在主串中不含指定的子串，find函数的返回值是（）。
正确答案:-1
第6题：
设有两个串T和P，求P在T中首次出现的位置的串运算称作【】
A．联接
B．求子串
C．子串定位
D．字符定位
正确答案：C
[解析]两个都是字符串，求一个字符串在另一个字符串中首次出现的位置的运算属于子串定位，而不是字符定位．
[解析]两个都是字符串，求一个字符串在另一个字符串中首次出现的位置的运算属于子串定位，而不是字符定位．
第7题：
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：
1．在串t和串s中，分别设比较的起始下标i=j=0。
2．如果串t和串s都还有字符，则循环执行下列操作：
（1）如果j=-l或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符；
（2）否则，将j向右滑动到next[j]的位置，即j =next[j]。
3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回-1。
其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。
【C代码】
（1）常量和变量说明
t，s：长度为lt和ls的字符串
next:next数组，长度为ls
（2）C程序
#include#include#include/*求next[]的值*/void get_next( int*next, char *s, int ls) { inti=0，j=-1; next[0]=-1;/*初始化next[0]*/ while(i< ls){/*还有字符*/ if(j==-1lls[i]==s[j]){/*匹配*/ j++; i++; if(s[i]==s[j]) next[i]= next[j]; else Next[i]= j; }else j = next[j]; }} int kmp( int*next, char *t ,char *s, int lt, int ls ) { Inti= 0,j =0 ; while(i < lt && （1） ){ if(j==-1 || （2） ){ i++ ; j++ ; }else （3） ;}if (j >= ls)return （4） ;else return-1;}
【问题1】（8分）
根据题干说明，填充C代码中的空（1）～（4）.
【问题2】（2分）
根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为It和Is，用O符号表示）。
【问题3】（5分）
根据C代码，字符串"BBABBCAC"的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为"AABBCBBABBCACCD"，子串为"BBABBCAC"，则函数Kmp的返回值是（7）。
【说明】
模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：
1．在串t和串s中，分别设比较的起始下标i=j=0。
2．如果串t和串s都还有字符，则循环执行下列操作：
（1）如果j=-l或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符；
（2）否则，将j向右滑动到next[j]的位置，即j =next[j]。
3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回-1。
其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。
【C代码】
（1）常量和变量说明
t，s：长度为lt和ls的字符串
next:next数组，长度为ls
（2）C程序
#include
【问题1】（8分）
根据题干说明，填充C代码中的空（1）～（4）.
【问题2】（2分）
根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为It和Is，用O符号表示）。
【问题3】（5分）
根据C代码，字符串"BBABBCAC"的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为"AABBCBBABBCACCD"，子串为"BBABBCAC"，则函数Kmp的返回值是（7）。
答案：
解析：
【问题1】
（1）：j
（3）：get_next(next, s, ls);
j=next[j];
（4）：i+1-ls;
【问题2】（2分）
（5）O(ls+lt)
【问题3】
（6）[-1, -1,1, -1, -1, 2, 0, 0]，
（7）6
（1）：j
（3）：get_next(next, s, ls);
j=next[j];
（4）：i+1-ls;
【问题2】（2分）
（5）O(ls+lt)
【问题3】
（6）[-1, -1,1, -1, -1, 2, 0, 0]，
（7）6
第8题：
设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。
A、求子串
B、联接
C、模式匹配
D、求串长
正确答案:C
第9题：
由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（）个。
- A、40320
- B、39600
- C、840
- D、780
- E、60
正确答案:D
第10题：
求子串在主串中首次出现的位置的运算称为（）。
正确答案:模式匹配