设字符串t的后缀数组和最长公共前缀数组分别为sa和lcp.对于非负整数0≤I≤r,t的后缀St和S
●试题五
阅读以下程序说明和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;
}
对于求取两个长度为n的字符串的最长公共子序列问题,利用(41)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。
A.贪心
B.分治
C.分支-限界
D.动态规划
对于求取两个长度为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中.
A.CIDR将网络前缀都相同的连续的IP地址组成“CIDR”地址块。
B.网络前缀越短,其地址块所包含的地址数就越少。
C.CIDR使用各种长度的“网络前缀”来代替分类地址中的网络号和子网号。
D.使用CIDR,查找路由表时可能会得到多个匹配结果,应当从匹配结果中选择具有最长网络前缀的路由。因为网络前缀越长,路由就越具体。
试题四(共15分)
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
模式匹配是指给定主串t和子串s,在主串t中寻找子串s的过程,其中s称为模式。
如果匹配成功,返回s在t中的位置,否则返回-1 。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下:
1.在串t和串s中,分别设比较的起始下标i=J=O
2.如果串t和串s都还有字符,则循环执行下列操作:
(1)如果j=-l或者t[i]-s[j],则将i和j分别加1,继续比较t和s的下一个字符;
(2)否则,将j向右滑动到next[j]的位置,即j =next[J]
3.如果s中所有字符均已比较完毕,则返回匹配的起始位置(从1开始);否则返回一1.
其中,next数组根据子串s求解。求解next数组的代码已由get_next函数给出。
【C代码】
(1)常量和变量说明
t,s:长度为悯铂Is的字符串
next:next数组,长度为Is
(2)C程序
include <stdio.h>
nclude <stdliB.h>
include <string.h>
/*求next【】的值*/
void get_next(int *next, char *s, int Is) {
int i=0,j=-1;
next[0]=-1;/*初始化next[0]*/
while(i< ils){/*还有字符*/
if(j=-1l ls[i]=s[j]){/*匹配*/
j++;
i++;
if(s[i]一s[jl)
next [i]- next[j];
else
Next[i]=j;
}
else
J= next[j];
}
}
int kmp(int *next, char *t ,char *s, int.lt, int Is )
{
inti= 0,j =0 ;
while (i<lt && (1 ) {
if(j=-1 II 2_) {
i++ ;
j ++ ;
} else
(3) :
}
if (j>= ls)
Retum (4)
else .
retum-1;
【问题1】(8分)
根据题干说明,填充C代码中的空(1)~(4).
【问题2】(2分)
根据题干说明和C代码,分析出kmp算法的时间复杂度为 (5)(主串和子的长度分别为It和Is,用O符号表示)。
【问题3】(5分)
根据C代码,字符串“BBABBCAC”的next数组元素值为 (6) (直接写素值,之间用逗号隔开)。若主串为“AABBCBBABBCACCD”,子串为“BBABBCAC则函数Kmp的返回值是 (7)
例如,若s所指字符串中的内容为“ABCDEFGl23456”,其中字符A的ASCIl码值为奇数,因此应当删除;字符8的ASCIl码值为偶数,但在数组中的下标为奇数,因此也应当删除;字符2的ASCIl码值为偶数,在数组中的下标也为偶数,因此不应当删除,其他依此类推。最后t所指的数组中的内容应是‘&39;246”。
注意:部分源程序给出如下。
请勿改动主函数main和其他函数中的任何内容,仅在函数fun的花括号中填入你编写的若干语句。
试题程序:
例如,若s所指字符串中的内容为“ABCDEFGl2345”,其中字符C的ASCIl码值为奇数,在数组中的下标为偶数,因此必须删除;而字符l的ASCIl码值为奇数,在数组中的下标为奇数,因此不应当删除,其他依此类推。最后t所指的数组中的内容应是“BDFl2345”。
注意:部分源程序给出如下。
请勿改动main函数和其他函数中的任何内容,仅在函数fun的花括号中填入你编写的若干语句。
试题程序: