首页 > 代码库 > 【算法导论学习-29】动态规划经典问题02：最长公共子序列问题（Longest common subsequence，LCS）

【算法导论学习-29】动态规划经典问题02：最长公共子序列问题（Longest common subsequence，LCS）

2024-07-21 22:29:12   224人阅读

问题描述：序列X={x1,x2,…,xn}，Y={y1,y2,…,yn}，当Z={z1,z2…,zn}是X的严格递增下标顺序（可以不连续）的子集，也是Y的严格递增下标顺序（可以不连续）的子集，则Z是X和Y的公共子序列。例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}，{B,C,A}、{B,C,B,A}、{B,D,A,B}都是X和Y的公共子序列。其中最长的公共子序列叫做Longest common subsequence，即经典的LCS。

  具体点：char[]xArray和char[] yArray是字符数组，长度分别为m、n，求他们的LCS

【分析】自顶向下分析，二维数组cTable[i][j]记录xArray[0~i],yArray[0~j]的最长公共子序列的长度，则cTable[m][n]记录xArray[0~m],yArray[0~n]的最长公共子序列的长度。

1）   如果xArray[m]=yArray[n]，表明最后一个元素xArray[m]是LCS中的元素，xArray[0~m],yArray[0~n]的最长公共子序列=xArray[0~m-1],yArray[0~n-1]的最长公共子序列+1，即cTable[m][n]=cTable[m-1][n-1]。

2）   如果xArray[m]!=yArray[n]，表明xArray[m]、yArray[n]都有可能是LCS中的元素，但不能同时是。如果xArray[m]可能是，则xArray[0~m],yArray[0~n]的最长公共子序列=xArray[0~m],yArray[0~n-1]的最长公共子序列；如果yArray[n]可能是，则xArray[0~m],yArray[0~n]的最长公共子序列=xArray[0~m-1],yArray[0~n]的最长公共子序列。即cTable[m][n]=max(cTable[m-1][n], cTable[m][n-1])。

状态递归方程为：


参考《算法导论》P394页伪代码，java实现如下：

[java] view plaincopyprint?
  1. /** 
  2.      * 创建时间：2014年9月3日 下午9:00:13 
  3.      * 项目名称：Test 
  4.      * @author Cao Yanfeng  Peking University
  5.      * @since JDK 1.6.0_21 
  6.      * 类说明：  最长公共子序列问题（Longest common subsequence,LCS）
  7.      */ 
  8.     public staticvoid main(String[] args) { 
  9.         // TODO 自动生成的方法存根 
  10.         String x="ABCBDABCBACABC"; 
  11.         String y="BDCABACABABCB"; 
  12.         int temp=getLCSLength(x, y); 
  13.         System.out.println("\n长度为："+temp); 
  14.     } 
  15.     public staticint getLCSLength(String x,String y) { 
  16.         char[] xArray=x.toCharArray(); 
  17.         char[] yArray=y.toCharArray(); 
  18.         int m=xArray.length; 
  19.         int n=yArray.length; 
  20.         int [][] bTable=newint[m][n]; 
  21.         /*cTable[i][j]记录xArray[0~i],yArray[0~j]的最长公共子序列的长度*/ 
  22.         int [][] cTable=newint[m+1][n+1]; 
  23.         for (int i =0; i <m; i++) { 
  24.             for (int j =0; j < n; j++) { 
  25.                 if (xArray[i]==yArray[j]) { 
  26.                     cTable[i+1][j+1]=cTable[i][j]+1; 
  27.                     bTable[i][j]=2;//相等标记为2 
  28.                 }else if (cTable[i][j+1]>=cTable[i+1][j]) { 
  29.                     cTable[i+1][j+1]=cTable[i][j+1]; 
  30.                     bTable[i][j]=1; 
  31.                 }else { 
  32.                     cTable[i+1][j+1]=cTable[i+1][j]; 
  33.                     bTable[i][j]=3; 
  34.                 } 
  35.                  
  36.             } 
  37.              
  38.         } 
  39.         System.out.print("最大子数组为："); 
  40.         printLCS(xArray, bTable, m-1,n-1); 
  41.         return cTable[m][n]; 
  42.     } 
  43.     /*输出最佳路径即最长公共子序列*/ 
  44.     public staticvoid printLCS (char[] xArray,int[][] bTable,int i,int j) { 
  45.         if (i==-1||j==-1) { 
  46.             return; 
  47.         } 
  48.         if (bTable[i][j]==2) { 
  49.             printLCS(xArray, bTable, i-1, j-1); 
  50.             System.out.print(xArray[i]); 
  51.         }else if (bTable[i][j]==1) { 
  52.             printLCS(xArray, bTable, i-1, j); 
  53.         }else { 
  54.             printLCS(xArray, bTable, i, j-1); 
  55.         } 
  56.     } 
  57.  
  58. } 

*****************************************

控制台输出：

最大子数组为：BCBACBACB

长度为：9

【算法导论学习-29】动态规划经典问题02：最长公共子序列问题（Longest common subsequence，LCS）


联系
我们