反馈

问题：
(共15分)<br/> 阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。<br/><br/> 【说明】<br/>下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度L及其在各字符串中的起始位置(L=0时不存在公共字串)。例如，字符串"the light is not bright tonight ” 与“ Tonight the light is not bright ”的最长公共子串为 "the light is not bright?，长度为22，起始位置分别为2和10。<br/><br/> 设A[1:M]表示由M个字符A[1]，A[2],…，A[M]依次组成的字符串；B[1:N]表示由N个字符B[1], B[2],…，B[N]依次组成的字符串，M≥N≥1。<br/><br/> 本流程图采用的算法是：从最大可能的公共子串长度值开始逐步递减，在A、B字符串中查找是否存在长度为L的公共子串,即在A、B字符串中分别顺序取出长度为L 的子串后，调用过程判断两个长度为L的指定字符串是否完全相同(该过程的流程略)。<br/><br/>

选项 ：
【问题：1.1】[流程图】<br/> <img style='width:100%;' src="https://files.lightsoft.tech/rkfiles/ruankao_work_version_0103/userfile/image/cxy2015-s-x-1d-1.png">

答案：


解析：
(1) N 或 min(M,N) (2) M-L+1 (3) N-L+1 (4) L-1 (5) L, I, J<br/>本题考查对算法流程图的理解和绘制能力。这是程序员必须具有的技能。<br/>本题的算法可用来检查某论文是否有大段抄袭了另一论文“the light is not bright tonight"是著名的英语绕口令，它与"onight the light is not bright"大同小异。<br/>由于字符串A和B的长度分别为M和N，而且M≥N≥1，所以它们的公共子串长度 L必然小于或等于N。题中采用的算法是，从最大可能的公共子串长度值L开始逐步递减，在A、B字符串中查找是否存在长度为L的公共子串。因此初始时，应将min (M, N)送L。或直接将N送L。(1) 处应填写N或min(M，N),或其他等价形式。<br/>对每个可能的L值，为查看A、B串中是否存在长度为L的公共子串，显然需要执行双重循环。A串中，长度为L的子串起始下标可以从1开始直到M-L+1 (可以用实例来检查其正确性)；B串中，长度为L的子串起始下标可以从1开始直到N-L+1。因此双重循环的始值和终值就可以这样确定，即(2) 处应填M-L+1，或等价形式；(3) 处应填N-L+1或等价形式(注意循环的终值应是最右端子串的下标起始值)。<br/>A串中从下标I开始长度为L的子串可以描述为A[I:I+L-1]; B串中从下标J开始长度为L的子串可以描述为A[J:J+L-1]。因此，双重循环体内，需要比较这两个子串(题中采用调用专门的函数过程或子程序来实现)。<br/>如果这两个子串比较的结果相同，那么就己经发现了 A、B串中最大长度为L的公共子串，此时，应该输出公共子串的长度值L、在A串中的起始下标I、在B串中的起 始下标J。因此，(5) 处应填L, I, J (可不计顺序)。<br/>如果这两个子串比较的结果不匹配，那么就需要继续执行循环。如果直到循环结束仍然没有发现匹配子串时，就需要将L减少1 ((4)处填L-1或其等价形式)。只要L非0,则还可以继续对新的L值执行双重循环。如果直到L=0,仍没有发现子串匹配，则表示A、B两串没有公共子串。 <br/>