计算两个字符串x和y的最长公共子串（Longest Common Substring）。
假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[i][j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。
c[i][j]满足最优子结构，其递归定义为：
计算所有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）。
正确答案及解析
正确答案
解析
【问题1】
（1）x[i-1]==y[j-1]
（2）max=c[i][j]
（3）c[i][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[i][j]=c[i-1][j-1]+1，此时根据递归式可以看到，所需的条件是x[i-1]=y[j-1]，因此第1空填写判断条件x[i-1]==y[j-1]。
第2空是在if(max＜c[i][j])跟随的大括号中，根据前后代码和此处的判断条件，当max小于当前时，应该改变max的值，并记录此时的maxi和maxj，此处缺少改变max的值，因此，第2空应该将当前最大值赋值给max，即max=c[i][j]。
第3空是第一个if语句的else选择，根据递归式，if（x[i-1]==y[j-1]）不满足时，属于其他情况，应该赋值为0，因此第3空填写c[i][j]=0。
而第4空是用于打印结果，由于maxi记录了子串末尾+1的位置信息，子串长度为max，所以用maxi-max定位至子串开始位置，以便打印子串，因此第4空填写i=maxi-max。
包含此试题的试卷
你可能感兴趣的试题
Advancements in （ ）have contributed to the growth of the automotive industry through the creation and evolution of self-driving vehicles.
-
- A.Artificial Intelligence
- B.Cloud Computing
- C.Internet of Things
- D.Big Data
- 查看答案
In project human resource management , （ ）is not a source of power for the project manager.
-
- A.referent power
- B.expert power
- C.reward power
- D.audit power
- 查看答案
At the project establishment stage , the feasibility study mainly includes techinical feasibility analysis , （ ）, operation environment feasibility analysis and other aspects of feasibility analysis.
-
- A.detail feasibility analysis
- B.opportunity analysis
- C.economic feasibility analysis
- D.risk analysis
- 查看答案
（ ）is a grid that shows the project resources assigned to each work package.
-
- A.Stakeholder engagement assessment matrix
- B.Requirements traceability matrix
- C.Probability and impact matrix
- D.Responsibility assignment matrix
- 查看答案
Xinhua News Agency reported in January 2022，Chian will further promote the developmet of a digital economy during the 14th Five-Year Plan eriod（2021-2025）. The plan also emphasized industrial （ ）transformation.
-
- A.digital
- B.networking
- C.intelligentize
- D.informatization
- 查看答案