个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java算法之最长公共子序列问题(LCS)实例分析由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

本文实例讲述了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的最长公共子序列相同.

代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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 );
   }
}

运行结果:

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

希望本文所述对大家java程序设计有所帮助.

原文链接：http://blog.csdn.net/u014755255/article/details/50571192 。

最后此篇关于Java算法之最长公共子序列问题(LCS)实例分析的文章就讲到这里了,如果你想了解更多关于Java算法之最长公共子序列问题(LCS)实例分析的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

24 4 0
文章推荐： 高傲霸气超拽个性签名女生 你现在能给我的只有现在
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com