Java算法之最長(zhǎng)公共子序列問題(LCS)實(shí)例分析

本文實(shí)例講述了Java算法之最長(zhǎng)公共子序列問題(LCS)。分享給大家供大家參考，具體如下：

問題描述：一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X= { x1, x2,…, xm}，則另一序列Z= {z1, z2,…, zk}是X的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列 {i1, i2,…, ik}，使得對(duì)于所有j=1,2,…,k有 Xij=Zj。例如，序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2,3,5,7}。給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。例如，若X= { A, B, C, B, D, A, B}和Y= {B, D, C, A, B, A}，則序列{B,C,A}是X和Y的一個(gè)公共子序列，序列{B,C,B,A}也是X和Y的一個(gè)公共子序列。而且，后者是X和Y的一個(gè)最長(zhǎng)公共子序列，因?yàn)閄和Y沒有長(zhǎng)度大于4的公共子序列。給定兩個(gè)序列X= {x1, x2, …, xm}和Y= {y1, y2, … , yn}，要求找出X和Y的一個(gè)最長(zhǎng)公共子序列。

問題解析：設(shè)X= { A, B, C, B, D, A, B},Y= {B, D, C, A, B, A}。求X，Y的最長(zhǎng)公共子序列最容易想到的方法是窮舉法。對(duì)X的多有子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列。由集合的性質(zhì)知，元素為m的集合共有2^m個(gè)不同子序列，因此，窮舉法需要指數(shù)級(jí)別的運(yùn)算時(shí)間。進(jìn)一步分解問題特性，最長(zhǎng)公共子序列問題實(shí)際上具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

設(shè)序列X={x1,x2,……xm}和Y={y1,y2,……yn}的最長(zhǎng)公共子序列為Z={z1,z2,……zk}。則有：

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

遞推關(guān)系：用c[i][j]記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi={x1,x2……xi}，Yj={y1,y2……yj}。當(dāng)i=0或j=0時(shí)，空序列是xi和yj的最長(zhǎng)公共子序列。此時(shí)，c[i][j]=0；當(dāng)i,j>0，xi=yj時(shí)，c[i][j]=c[i-1][j-1]+1；當(dāng)i,j>0，xi!=yj時(shí)，
c[i][j]=max{c[i][j-1],c[i-1][j]}，由此建立遞推關(guān)系如下：

構(gòu)造最優(yōu)解：由以上分析可知，要找出X={x1,x2,……xm}和Y={y1,y2,……yn}的最長(zhǎng)公共子序列,可以按一下方式遞歸進(jìn)行：當(dāng)xm=yn時(shí)，找出xm-1和yn-1的最長(zhǎng)公共子序列，然后在尾部加上xm(=yn)即可得X和Y的最長(zhǎng)公共子序列。當(dāng)Xm!=Yn時(shí)，必須解兩個(gè)子問題，即找出Xm-1和Y的一個(gè)最長(zhǎng)公共子序列及X和Yn-1的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者為X和Y的最長(zhǎng)公共子序列。設(shè)數(shù)組b[i][j]記錄c[i][j]的值由哪一個(gè)子問題的解得到的，從b[m][n]開始，依其值在數(shù)組b中搜索，當(dāng)b[i][j]=1時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列是由Xi-1和Yj-1的最長(zhǎng)公共子序列在尾部加上xi所得到的子序列。當(dāng)b[i][j]=2時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列與Xi-1和Yj-1的最長(zhǎng)公共子序列相同。當(dāng)b[i][j]=3時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列與Xi和Yj-1的最長(zhǎng)公共子序列相同。

代碼如下：

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("億速云測(cè)試結(jié)果：");
    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的最長(zhǎng)公共子序列是：");
    LCS(b, x, x.length - 1, y.length - 1);
  }
}

運(yùn)行結(jié)果：

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。