最长公共子序列（不要求连续）求长度,时间复杂度O(n+m)
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/24 08:22:08
最长公共子序列（不要求连续）求长度,时间复杂度O(n+m)
最长公共子序列（不要求连续）
求长度,时间复杂度O(n+m)
最长公共子序列（不要求连续）求长度,时间复杂度O(n+m)
得到字符串m1,m2后,有一个为空则子列为空.
如果都不为空,开始下面的步骤.
求得两列的长度分别为n1,n2.
动态生n2行n1列矩阵（二维数组）.
取m2中每个元素（记位置为i）与m1中元素（记位置为j）逐个比较,如果相等则为矩阵中相应行列坐标的元素赋值为1,否则为0（可用循环嵌套完成）.
比如m1(abc0cbad) m2(cba1abc)两串的话,可以得到如图所示矩阵.
然后,不难看出,要进行如下步骤.
定义max,用来记录最大子列中元素个数.
定义数组l[n2],用来记录最大子列的首字符地址（因为可能有不同最大子列,故用数组,而不是单个变量）.
判断矩阵中每一个元素,是否为1,如果是则记下此时行地址到l数组,然后判断相对于这个元素的下一行下一列的元素是否为1,如果是则继续判断,一直到为0.记下此次判断（即一个while循环）中“1”的个数n,存入变量max.
对于矩阵中的每一个元素都这么判断,如果判断中n的值大于max那么把n付给max,同时把这个子列的首地址付给l[0],l[0]后面的元素全赋值为-1.如果,某次判断得到的n与max相同,即有相同最大子列,那么把它的首地址存入l数组的下一个位置.
当这个矩阵的每一个元素都判断完毕后,会得到max,和数组l,然后用循环做如下输出过程： 依次以l数组中的每个元素为首地址,输出m2字符串中以相应序号开头的max个字符,那么完成所有最大子列的输出.
昨天失眠了,一直到今天凌晨3点多,脑袋浑浑噩噩的,本想帮你敲代码,可是脑力不支了,估计敲出来也乱,还有问题的话,再讨论452032545