题目内容
（请给出正确答案）
[主观题]
对于求取两个长度为n的字符串的最长公共子序列问题，利用（41)策略可以有效地避免子串最长公共子序
对于求取两个长度为n的字符串的最长公共子序列问题，利用(41)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。
A．贪心
B．分治
C．分支-限界
D．动态规划
查看答案
如果结果不匹配，请 联系老师 获取答案
题目内容
（请给出正确答案）
如果结果不匹配，请 联系老师 获取答案
题目内容
（请给出正确答案）
对于求取两个长度为n的字符串的最长公共子序列问题，利用(41)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。
A．贪心
B．分治
C．分支-限界
D．动态规划
如果结果不匹配，请 联系老师 获取答案
更多“对于求取两个长度为n的字符串的最长公共子序列问题，利用（41…”相关的问题
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用(24)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。串 ＜1，0，0，1，O，1，0，1＞和＜0，1，0，1，1,0,1，1＞的最长公共子序列的长度为(25)。
A．分治
B．贪心
C．动态规划
D．分支—限界
算法设计:设计一个算法,找出给定序列x和y的包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x、y和约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的包含s为其子串的最长公共子序列的长度输出到文件output.txt中.
![问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及一个长度为p](https://img2.soutiyun.com/ask/2021-01-05/97870096903162.png)
![问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及一个长度为p](https://img2.soutiyun.com/ask/2021-01-05/978700980362268.png)
●试题五
阅读以下程序说明和C程序，将应填入(n)处的子句，写在答卷纸的对应栏内。
【程序说明】
函数int commstr(char *str1,char *str2,int *sublen)从两已知字符串str1和str2中，找出它们的所有最长的公共子串。如果最长公共子串不止1个，函数将把它们全部找出并输出。约定空串不作为公共子串。
函数将最长公共子串的长度送入由参数sublen所指的变量中，并返回字符串str1和str2的最长公共子串的个数。如果字符串str1和str2没有公共子串，约定最长公共子串的个数和最长公共子串的长度均为0。
【程序】
int strlen(char *s)
{char *t=s；
while(*++)；
return t-s-1;
}
intcommstr(char)*str1,char *str2,int *sublen
{char*s1,*s2；
int count=0,len1,len2,k,j,i,p;
len1=strlen(str1);
len2=strlen(str2);
if(len1＞len2)
{s1=str1;s2=str2;}
else{len2=len1;s1=str2;s2=str1;}
for(j=len2;j＞0;j--)/*从可能最长子串开始寻找*
{for(k=0; (1) ＜=len2;k++)/*k为子串s2的开始位置*/
{for(i=0;s1［ (2) ］!='＼0';i++;)/* i为子串s1的开始位置*/
{/* s1的子串与s2的子串比较*/
for(p=0;p＜j)&& (3) ;p++);
if ((4) )/*如果两子串相同*/
{for(p=0);p＜j;p++}/*输出子串*/
printf("%c",s2［k+p］);
printf("＼n");
count++；/* 计数增1*/
}
}
}
if (count＞0)break;
*sublen=(count＞0)？ (5) :0;
return count;
}
算法设计:设计一个算法,找出给定字符串X的最长重复子串.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出字符串X.
结果输出:将计算出的字符串X的最长重复子串输出到文件output.txt中.
文件的第1行是最长重复子串的长度.文件的第2行是最长重复子串.
在一般情况下,字符串A和B的长度不一定相同.字符串A的扩展是在A中插入若干空格字符所产生的字符串.在字符串A和B的所有长度相同的扩展中,有一对距离最小的扩展,该距离称为字符串A和B的扩展距离.
对于给定的字符串4和B,试设计一个算法,计算其扩展距离.
算法设计:对于给定的字符串A和B,计算其扩展距离.
数据输入:由文件input.txt给出输入数据.第1行是字符串A,第2行是字符串B,第3行是空格与其他字符的距离定值k.
结果输出:将计算出的字符串A和B的扩展距离输出到文件output.txt.
