软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2021/12/14）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2021/12/14

点击查看：更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容（2021/12/14）

试题四（共15分）
   阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
   计算两个字符串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［i］［0］=0;
for (i =1; i<= m; i++)    {
     for (j=1; j<= n; j++)    {
        If (    (1)    )    {
c[il[j] = c[i - l][j - i] + 1;
if(max<c[il[j] {
        (2)   :
    maxi = i;
    maxj =j;
 }
}
else     (3)    ;
       }
   }
    retum  max;
}    
void printLCS(int max, char *x) {
         int i= 0;
      if (max = 0)        retum;
     For （  (4)    ； i < maxi; i++)
}
void main（）{
 Char* x= "ABCADAB";
 Char*y= "BDCABA";
  int max= o;
 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）  （用0符号表示）。
【问题3】（3分）
 根据题干说明和以上C代码，输入字符串x= "ABCADAB’，'y="BDCABA",则输出为   （7）。