首页
登录
从业资格
阅读下列说明和 C 代码,回答问题 1 至问题 3 ,将解答写在对应栏内。【说明
阅读下列说明和 C 代码,回答问题 1 至问题 3 ,将解答写在对应栏内。【说明
练习题库
2022-08-02
78
问题
阅读下列说明和 C 代码,回答问题 1 至问题 3 ,将解答写在对应栏内。【说明】计算两个字符串 x 和 y 的最长公共子串( Longest Common Substring )。假设字符串 x 和字符串 y 的长度分别为 m 和 n ,用数组 c 的元素 c
[j] 记录 x 中前 i 个字符和 y 中前 j 个字符的最长公共子串的长度。 c
[j]满足最优子结构,其递归定义为:
计算所有 c
[j](0 ≤ i ≤ m , 0 ≤ j ≤ n) 的值,值最大的 c
[j] 即为字符串 x 和 y 的最长公共子串的长度。根据该长度即 i 和 j ,确定一个最长公共子串。 【 C代码】 (1) 常量和变量说明x , y :长度分别为 m 和 n 的字符串c
[j] :记录 x 中前 i 个字符和 y 中前 j 个字符的最长公共子串的长度max : x 和 y 的最长公共子串的长度maxi, maXj :分别表示 x 和 y 的某个最长公共子串的最后一个字符在 x 和 y 中的位置(序号) (2)C 程序 #include
选项
答案
解析
【问题1】(1)x[i-1]= =y[j-1](2)max=c
[j](3)c
[j]=0 (4)i=maxi-max【问题2】(动态规划、 O(m×n)或O(mn)【问题3】AB根据题干和C代码,计算出下表的值。
最大值为2。在计算过程中,我们记录第一个最大值,即表中阴影部分元素,因此得到最长公共子串为AB。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2408434.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
程序中全局变量的存储空间在()分配。A.代码区 B.静态数据区 C.栈区
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某航空售票
阅读下列说明,回答问题1和问题2,将解答填入答题纸的对应栏内。【说明】某图书馆
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某健身俱乐
阅读下列说明,回答问题1至问题3;将解答填入答题纸的对应栏内。【说明】某销售公司
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某家电
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某电视台
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某会议
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某医
随机试题
Formostpeople,theideaofgivingapresentationtoagroupofpeopleisa
TheInternetcanmakethenewsmoredemocratic,givingthepublicachancet
Contrasttoresearchers’expectations,dysfunctionalfamilyrelationshipsand
简述农业与农村经济可持续发展的对策。
在细菌的革兰氏涂色中,用于脱色的溶液是( )。A.结晶紫 B.酒精 C.番
当基金管理人认为兑付投资者的赎回申请有困难,或认为兑付投资者的赎回申请进行的资产
药品不良反应监测报告范围下列哪项是错误的A.中药饮片不良反应监测的问题较复杂,
关于内生肌酐清除率标本采集前饮食护理正确的是A:仅试验日进食低蛋白饮食即可 B
广义的信贷期限通常分为()。A.提款期 B.谈判期 C.宽限期 D.申请
下列哪些请求不适用诉讼时效?A:当事人请求撤销合同B:当事人请求确认合同无效
最新回复
(
0
)