服务器之家

服务器之家 > 正文

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

时间:2021-02-21 11:09     来源/作者:萌神哆啦A梦

本文实例讲述了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是xyn-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

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部