答案及解析：[问答题]计算两个字符串x和y的最长公共子串（Longest Common Substring）。假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[i][j]记录x中前i个字符和y中前j个字符的最长公

问题：

[问答题] 计算两个字符串x和y的最长公共子串（Longest Common Substring）。假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[i][j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。c[i][j]满足最优子结构，其递归定义为：中级软件设计师,历年真题,2015年下半年（下午）《软件设计师》真题

计算所有c[i][j](0≤i≤m，0≤j≤n)的值，值最大的c[i][j]即为字符串x和y的最长公共子串的长度。根据该长度即i和j，确定一个最长公共子串。【C代码】（1）常量和变量说明x，y：长度分别为m和n的字符串c[i][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[i][0]=0;for(i=1;i＜=n;i++)c[0][i]=0;for(i=1;i＜=m;i++){for(j=1;j＜=n;j++){if((1)){c[i][j]=c[i-1][j-1]+1;if(max＜c[i][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[i]);}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）。

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题