軟件設計師案例分析當天每日一練試題地址：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4

往期軟件設計師每日一練試題匯總：www.xomuzic.com/class/27/e4_1.html

軟件設計師案例分析每日一練試題（2022/9/11）在線測試：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4&day=2022/9/11

點擊查看：更多軟件設計師習題與指導

軟件設計師案例分析每日一練試題內容（2022/9/11）

試題四（共15分）
   閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對應欄內。
【說明】
   計算兩個字符串x和y的最長公共子串（Longest Common Substring）。
   假設字符串x和字符串y的長度分別為m和n，用數組c的元素c[i][j]記錄x中前i
個字符和y中前j個字符的最長公共子串的長度。
   c[i][j]滿足最優(yōu)子結構，其遞歸定義為：
 


   計算所有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）。