2. 从业资格
  3. 计算两个字符串x和y的最长公共子串（Longest Common Substri

计算两个字符串x和y的最长公共子串（Longest Common Substri

最全题库2022-08-02  45
问题 计算两个字符串x和y的最长公共子串（Longest Common Substring）。假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。c[j]满足最优子结构，其递归定义为：计算所有c[j](0≤i≤m，0≤j≤n)的值，值最大的c[j]即为字符串x和y的最长公共子串的长度。根据该长度即i和j，确定一个最长公共子串。【C代码】（1）常量和变量说明x，y：长度分别为m和n的字符串c[j]：记录x中前i个字符和y中前j个字符的最长公共子串的长度max：x和y的最长公共子串的长度maxi,maXj：分别表示x和y的某个最长公共子串的最后一个字符在x和y中的位置（序号）（2）C程序#include＜stdio.h>#include＜string.h>int c[50][50];int maxi;int maxj;int lcs(char*x,int m,char*y,int n){int i,j;int max=0;maxi=0;maxj=0;for(i=0;i＜=m;i++)c[0]=0;for(i=1;i＜=n;i++)c[0]=0;for(i=1;i＜=m;i++){for(j=1;j＜=n;j++){if((1)){c[j]=c[i-1][j-1]+1;if(max＜c[j]){(2);maxi=i;maxj=j;}}else(3);}}return max;}void printLCS(int max,char*x){int i=0;if(max==0)return;for((4);i＜maxi;i++)printf("%c",x);}void main（　　）{char*x="ABCADAB";char*y="BDCABA";int max=0;int m=strlen(x);int n=strlen(y);max=lcs(x,m,y,n);printLCS(max,x);}【问题1】（8分）根据以上说明和C代码，填充C代码中的空（1）～（4）。【问题2】（4分）根据题干说明和以上C代码，算法采用了（5）设计策略。分析时间复杂度为（6）（用O符号表示）。【问题3】（3分）根据题干说明和以上C代码，输入字符串x="ABCADAB'，'y="BDCABA"，则输出为（7）。
选项
答案
解析 【问题1】
（1）x[i-1]==y[j-1]
（2）max=c[j]
（3）c[j]=0
（4）i=maxi-max
【问题2】
（5）动态规划法
（6）O(m*n)
【问题3】
（7）AB
首先对于C语言算法题，一般的解题思路是先解决除程序填空以外的问题，这些问题弄清楚，有利于程序填空部分的分析。
第一步，分析程序所采用的算法，常见的算法包括：分治法、动态规划法、回溯法、贪心法。本题中要求的是两个串的最长公共子串，在程序中采用了数组来记录子问题的中间结果，这一特征与动态规划法的做法非常吻合，所以应选动态规划法。
第二步，解决“输入字符串x="ABCADAB’，'y="BDCABA"，则输出为（7）”的问题，该问题相对容易解决，因为题目已告知程序的作用是求最长公共子串，而且从程序的输出函数可以看出，要输出的，只有子串，没有其他信息，所以我们只需要手动求两个串的公共子串，并写出答案即可。两个串第一个公共子串明显是“AB”，所以输出的结果为“AB”。
第三步，求时间复杂度，由于程序中最多双重循环，其中外层循环的规模为m，而内层循环的规模为n，所以时间复杂度为O(m*n)。
第四步，也是最难的一步，是解决程序填空的问题。动态规划的问题，一般都会给出递归定义式，这个式子，往往是多个空的关键点。以本题为例：
第1空是判断的条件，输出的结果是c[j]=c[i-1][j-1]+1，此时根据递归式可以看到，所需的条件是x[i-1]=y[j-1]，因此第1空填写判断条件x[i-1]==y[j-1]。
第2空是在if(max＜c[j])跟随的大括号中，根据前后代码和此处的判断条件，当max小于当前时，应该改变max的值，并记录此时的maxi和maxj，此处缺少改变max的值，因此，第2空应该将当前最大值赋值给max，即max=c[j]。
第3空是第一个if语句的else选择，根据递归式，if（x[i-1]==y[j-1]）不满足时，属于其他情况，应该赋值为0，因此第3空填写c[j]=0。
而第4空是用于打印结果，由于maxi记录了子串末尾+1的位置信息，子串长度为max，所以用maxi-max定位至子串开始位置，以便打印子串，因此第4空填写i=maxi-max。
转载请注明原文地址:https://tihaiku.com/congyezige/2409841.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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