文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java算法之最长公共子序列问题(LCS)实例分析

2023-05-30 20:05

关注

本文实例讲述了Java算法之最长公共子序列问题(LCS)。分享给大家供大家参考,具体如下:

问题描述:一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X= { x1, x2,…, xm},则另一序列Z= {z1, z2,…, zk}是X的子序列是指存在一个严格递增的下标序列 {i1, i2,…, ik},使得对于所有j=1,2,…,k有 Xij=Zj。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X= { A, B, C, B, D, A, B}和Y= {B, D, C, A, B, A},则序列{B,C,A}是X和Y的一个公共子序列,序列{B,C,B,A}也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列,因为X和Y没有长度大于4的公共子序列。给定两个序列X= {x1, x2, …, xm}和Y= {y1, y2, … , yn},要求找出X和Y的一个最长公共子序列。

问题解析:设X= { A, B, C, B, D, A, B},Y= {B, D, C, A, B, A}。求X,Y的最长公共子序列最容易想到的方法是穷举法。对X的多有子序列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列。由集合的性质知,元素为m的集合共有2^m个不同子序列,因此,穷举法需要指数级别的运算时间。进一步分解问题特性,最长公共子序列问题实际上具有最优子结构性质。

设序列X={x1,x2,……xm}和Y={y1,y2,……yn}的最长公共子序列为Z={z1,z2,……zk}。则有:

(1)若xm=yn,则zk=xm=yn,且zk-1是Xm-1和Yn-1的最长公共子序列。
(2)若xm!=yn且zk!=xm,则Z是Xm-1和Y的最长公共子序列。
(3)若xm!=yn且zk!=yn,则Z是X和Yn-1的最长公共子序列。
其中,Xm-1={x1,x2……xm-1},Yn-1={y1,y2……yn-1},Zk-1={z1,z2……zk-1}。

递推关系:用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中,Xi={x1,x2……xi},Yj={y1,y2……yj}。当i=0或j=0时,空序列是xi和yj的最长公共子序列。此时,c[i][j]=0;当i,j>0,xi=yj时,c[i][j]=c[i-1][j-1]+1;当i,j>0,xi!=yj时,
c[i][j]=max{c[i][j-1],c[i-1][j]},由此建立递推关系如下:

Java算法之最长公共子序列问题(LCS)实例分析

构造最优解:由以上分析可知,要找出X={x1,x2,……xm}和Y={y1,y2,……yn}的最长公共子序列,可以按一下方式递归进行:当xm=yn时,找出xm-1和yn-1的最长公共子序列,然后在尾部加上xm(=yn)即可得X和Y的最长公共子序列。当Xm!=Yn时,必须解两个子问题,即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者为X和Y的最长公共子序列。设数组b[i][j]记录c[i][j]的值由哪一个子问题的解得到的,从b[m][n]开始,依其值在数组b中搜索,当b[i][j]=1时,表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列在尾部加上xi所得到的子序列。当b[i][j]=2时,表示Xi和Yj的最长公共子序列与Xi-1和Yj-1的最长公共子序列相同。当b[i][j]=3时,表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。

代码如下:

package LCS;public class LCS {  public static int[][] LCSLength ( String[] x, String[] y) {    int m = x.length;    int n = y.length;    int[][] b = new int[x.length][y.length];    int[][] c = new int[x.length][y.length];    for(int i = 1; i < m; i++) {      c[i][0] = 0;    }    for(int i = 1; i < n; i++) {      c[0][i] = 0;    }    for(int i = 1; i < m; i++) {      for(int j = 1; j < n; j++) {        if(x[i] == y[j]) {          c[i][j] = c[i-1][j-1] + 1;          b[i][j] = 1;        }        else if(c[i-1][j] >= c[i][j-1]) {          c[i][j] = c[i-1][j];          b[i][j] = 2;        }        else {          c[i][j] = c[i][j-1];          b[i][j]=3;        }      }    }    return b;  }  public static void LCS(int[][] b, String[] x, int i, int j) {    if(i == 0|| j == 0) return;    if(b[i][j] == 1) {      LCS(b,x,i - 1, j - 1);      System.out.print(x[i] + " ");    }    else if(b[i][j] == 2) {      LCS(b,x,i - 1, j);    }    else LCS(b,x,i, j-1);  }  public static void main(String args[]) {    System.out.println("编程网测试结果:");    String[] x = {" ","A", "B", "C", "B", "D", "A", "B"};    String[] y = {" ","B", "D", "C", "A", "B", "A"};    int[][] b = LCSLength(x, y);    System.out.println("X和y的最长公共子序列是:");    LCS(b, x, x.length - 1, y.length - 1);  }}

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 资料下载
  • 历年真题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯