首页
登录
从业资格
阅读下列说明和 C 代码,回答问题 1 至问题 3 ,将解答写在对应栏内。【说明
阅读下列说明和 C 代码,回答问题 1 至问题 3 ,将解答写在对应栏内。【说明
练习题库
2022-08-02
57
问题
阅读下列说明和 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://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,将解答填入答题纸的对应栏内。【说明】某医
随机试题
Onthewholeit’sagoodbook;anditwouldbeunwiseto______thosesmalldefect
When______atthedoor,shewasgivenawarmwelcome.A、appearsB、appearingC、toa
[originaltext]M:OK,soifyou’rereadytotaketheplunge,ifyouwannagetou
Whenwilltheydiscusstheagenda?[audioFiles]audio_ezfz2004_003[/audioFiles]A、
A.宽深比等于3的矩形、正方形、等边三角形 B.宽深比等于3的矩形、等边三角形
以太网可以传送最大的TCP段为()字节A.1480 B.1500 C
10.中国共产党人的初心和使命是________。
ISO9000系列标准是由ISO发布的,ISO的中文全称是( ).A.国际标准
完整的计算机系统由()两大部分组成。A.应用软件和系统软件 B.随机存储器和
更年安片的功能是A.滋阴补血,补心安神 B.滋阴清热,除烦安神 C.疏肝解郁
最新回复
(
0
)