2. 计算机
  3. 阅读以下说明和流程图，填补流程图中的空缺。 【说明】 下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度L及其在各字符串中的起始位置(L一O时不存在公共字串)。例如，字符串“Thelight is not bright

阅读以下说明和流程图，填补流程图中的空缺。 【说明】 下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度L及其在各字符串中的起始位置(L一O时不存在公共字串)。例如，字符串“Thelight is not bright

admin2016-09-08  70
问题 阅读以下说明和流程图，填补流程图中的空缺。
【说明】
    下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度L及其在各字符串中的起始位置(L一O时不存在公共字串)。例如，字符串“Thelight is not bright tonight”与“Tonight the light is not bri．ght”的最长公共子串为“he light isnot bright”，长度为22，起始位置分别为2和10。
    设A[1：M]表示由M个字符A[l]，A[2]，…，A[M]依次组成的字符串；B[1：N]表示由N个字符B[l]，B[2]，…，B[N]依次组成的字符串，M≥N≥l。
    本流程图采用的算法是：从最大可能的公共子串长度值开始逐步递减，在A、B字符串中查找是否存在长度为L的公共子串，即在A、B字符串中分别顺序取出长度为L的子串后，调用过程判断两个长度为L的指定字符串是否完全相同(该过程的流程略)。
【流程图】
选项
答案(1)N或min(M，N) (2)M一L+1 (3)N一L+1 (4)1一1 (5)L，I，J
解析 本题考查对算法流程图的理解和绘制能力。这是程序员必须具有的技能。
    本题的算法可用来检查某论文是否有大段抄袭了另一论文。“The light is not brighttonight”是著名的英语绕口令，它与“Tonight the light is not bright”大同小异。
    由于字符串A和B的长度分别为M和N，而且M≥N≥l，所以它们的公共子串长度L必然小于或等于N。题中采用的算法是，从最大可能的公共子串长度值L开始逐步递减，在A、B字符串中查找是否存在长度为L的公共子串。因此，初始时，应将min(M， N)送L，或直接将N送L。(1)处应填写N或min(M，N)，或其他等价形式。
    对每个可能的L值，为查看A、B串中是否存在长度为L的公共子串，显然需要执行双重循环。A串中，长度为L的子串起始下标可以从1开始直到M一L+1(可以用实例来检查其正确性)；B串中，长度为L的子串起始下标可以从1开始直到N一L+1。因此双重循环的始值和终值就可以这样确定，即(2)处应填M一L+l，或等价形式；(3)处应填N一L+l或等价形式(注意循环的终值应是最右端子串的下标起始值)。
    A串中从下标I开始长度为L的子串可以描述为A[I：I+L一1]；B串中从下标J开始长度为L的子串可以描述为A[J：J+L一l]。因此，双重循环体内，需要比较这两个子串(题中采用调用专门的函数过程或子程序来实现)。
    如果这两个子串比较的结果相同，那么就已经发现了A、B串中最大长度为L的公共子串，此时，应该输出公共子串的长度值L、在A串中的起始下标I、在B串中的起始下标J。因此，(5)处应填L，I，J(可不计顺序)。
    如果这两个子串比较的结果不匹配，那么就需要继续执行循环。如果直到循环结束仍然没有发现匹配子串时，就需要将L减少l((4)处填L一l或其等价形式)。只要L非0，则还可以继续对新的L值执行双重循环。如果直到L=0，仍没有发现子串匹配，则表示A、B两串没有公共子串。
转载请注明原文地址:https://www.kaotiyun.com/show/59jZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)