求两个数列的所有公共子序列.算法设计 求两个数列的所有公共子序列 注意 不是最长公共子序列.时间复杂度越小越好一共就20

求两个数列的所有公共子序列.
算法设计 求两个数列的所有公共子序列 注意 不是最长公共子序列.时间复杂度越小越好
一共就20个财富值,或提供下思路.
cai781028 1年前 已收到2个回答 举报

大家说我爱面子 春芽

共回答了14个问题采纳率:92.9% 举报

先判断出两个数列的元素个数谁少
再逐个判断元素个数少的那个数列中的每一个元素是否是另一个当中的元素,从而得到最长公共子序列
最后,从最长公共子序列中循环列出所有公共子序列.

1年前 追问

4

cai781028 举报

谢谢你的回答。 最长公共子序列循环 不能列出所有公共子序列吧?比如一个序列式BCADE 一个是EBDCA 最长公共子序列是BCA 但是不包括E啊。明显E也是公共子序列

举报 大家说我爱面子

编程比较是用双重循环来进行的. 1.用B与第一个E比较,不是,再用B跟第二个比较是的,赋值给新变量,跳出内循环 2.用C跟第一个E比较,不是,再用C跟第二个比较,...... 按此方法,怎么会E没有包括进去呢?

cai781028 举报

哦 这样啊 。这种算法的时间复杂度是不是有点高了?我qq 494423162 求指导下 万分感激。

qizhihe 幼苗

共回答了13个问题采纳率:69.2% 举报

希望有点启发,可能应该是要找出所有尽可能长的公共子序列,比如下面的两个序列
S1:1 2 3 4 5 6 7 8 9 10
S2:1 2 3 X 5 6 7 8 X
尽可能长的公共子序列有两个:1 2 3和5 6 7 8。找到了“所有尽可能长的公共子序列”,那么每个“尽可能长的公共子序列”的任意子序列即为所求。这样是不是稍微容易些了?不是的吧。S1和S2最长公共子序列是12...

1年前

2
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 18 q. 0.015 s. - webmaster@yulucn.com