阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】计算两个字符串x和y的最长公共子串(Lo
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】计算两个字符串x和y的最长公共子串(LongestCommonSubstring)。假设字符串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>intc[50][50];intmaxi;intmaxj;intlcs(char
*x,intm,char*y,intn){inti,j;intmax=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)
;}}returnmax;}void
printLCS(intmax,char*x){inti=0;if(max==0)return;for(
(4);i＜maxi;i++)printf("%c",x[i]);}voidmain(){char*x="ABCADAB";char*y="BDCABA";intmax=0;intm=strlen(x);intn=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】（8分）答案：（1）x[i-1]= =y[j-1] （2）max=c[i][j]（3）c[i][j]=0 （4）i=maxi-max
【问题2】（4分）答案：动态规划、 O(m×n)或O(mn)
【问题3】（3分）答案：AB根据题干和C代码，计算出下表的值。
最大值为2。在计算过程中，我们记录第一个最大值，即表中阴影部分元素，因此得到最长公共子串为AB。
