算法课题——最长公共子序列

最长公共子序，到底啥是最长公共子序列？子序列跟公共子串有啥区别？

  最长公共子序列：是两个或多个系列的公共的最长的子序列，在子序列当中，下标呈严格的递增序列；

  最长公共子串：是在最长公共子序列当中，下标呈相连的子序列当中最长的子串。

  例如：X={A,B,C,D,A,B},Y={B,C,B,D,B}.最长公共子序列Z={B,C,D,B},最长公共子串C={B,C}.

   基本定理：

   若两个序列X={x1,x2,…,xn}，Y={y1,y2,…，ym}的最长公共子序列Z={z1,z2,…,zk}；

•  若xn=ym,则zk=xn=ym,且Zk-1 是Xn-1与Ym-1的最长公共子序列；
• 若xn!=ym,zk!=xn,则Z 是Xn-1与Y 的最长公共子序列；
• 若xn!=ym,zk!=ym,则Z是X与Ym-1的最长公共子序列。

 

   那么问题来了，在序列当中怎么求最长公共子序列？

   最常用的两种方法：穷举法，动态规划法。

   穷举法：求两个序列X={x1,x2,…,xn}，Y={y1,y2,…，ym}的最长公共子序列。列出X的所有子序列，再用那个子序列去匹配Y的子序列，匹配成功则记录下该子序列的长度和该子序列，待全部的子序列匹配完毕就可以找到X,Y两序列的最长公共子序列。这样的时间复杂度有点儿大的惊人，O(2^n*2^m).

   动态规划法：求两个序列X={x1,x2,…,xn}，Y={y1,y2,…，ym}的最长公共子序列。

    1、若Xn=Ym ,则先求出Xn-1与Ym-1的最长公共子序列，再加上Xn就是X,Y的最长公共子序列了；

    2、若Xn！=Ym,则先求出X与Ym-1，Xn-1与Y的最长公共子序列，再去两者的最长子序列即可。

                 |  0            i,j=0

    推导式：C[i][j]|  C[i-1][j-1]+1  i,j>0,Xi=Yj

                 |  Max{C[i][j-1],C[i-1][j]}

                 |               i,j>0,Xi!=Yj

 源码：

package com.usc.lilin.LCSProblem;

/**
 * 算法课题探究
 * 最长公共子序列
 * @author gaosi
 *
 */
public class LCSProblem {
	
	
	  public static void main(String[] args)
	  {
	    //保留空字符串是为了getLength()方法的完整性也可以不保留
	    //但是在getLength()方法里面必须额外的初始化c[][]第一个行第一列
	    String[] x = {"", "A", "B", "C", "B", "D", "A", "B"};
	    String[] y = {"", "B", "D", "C", "A", "B", "A"};
	    
	    int[][] b = getLength(x, y);
	    
	    //以x数组为标准比较，数组x,y的最大下标为x.length-1, y.length-1；
	    Display(b, x, x.length-1, y.length-1);
	  }
	  /**
	   * 获取每个数据的比较情况
	   * @param x
	   * @param y
	   * @return 返回一个记录决定搜索的方向的数组
	   */
	  public static int[][] getLength(String[] x, String[] y)
	  {	//数组b用来存放0,1，-1标记
	    int[][] b = new int[x.length][y.length];
	    int[][] c = new int[x.length][y.length];
	    
	    for(int i=1; i<x.length; i++)
	    {
	      for(int j=1; j<y.length; j++)
	      {
	        //对应第一个性质(如果某位置字符数组的内容相同，将其对应队列位置赋值为1)
	        if( x[i] == y[j])
	        {
	          c[i][j] = c[i-1][j-1] + 1;
	          b[i][j] = 1;
	        }
	        //对应第二或者第三个性质(如果其队列c左边数大于上边的，将其对应位置赋值为0)
	        else if(c[i-1][j] >= c[i][j-1])
	        {
	        	//对应图中箭头上移
	          c[i][j] = c[i-1][j];
	          b[i][j] = 0;
	        }
	        //对应第二或者第三个性质（如果其队列c左边数小于上边的，将其对应位置赋值为-1）
	        else
	        { 
	        	//对应图中箭头左移
	          c[i][j] = c[i][j-1];
	          b[i][j] = -1;
	        }
	      }
	    }	
	    
	    return b;
	  }
	  /**
	   * 回溯的基本实现，采取递归的方式
	   * @param b 标志每个元素的比较情况的二维数组
	   * @param x 序列
	   * @param i 递归的大小
	   * @param j 递归的大小
	   */
	  public static void Display(int[][] b, String[] x, int i, int j)
	  {
	    if(i == 0 || j == 0)
	      return;
	    
	    if(b[i][j] == 1)
	    {
	      Display(b, x, i-1, j-1);
	      System.out.print(x[i] + " ");
	    }
	    else if(b[i][j] == 0)
	    {
	      Display(b, x, i-1, j);
	    }
	    else if(b[i][j] == -1)
	    {
	      Display(b, x, i, j-1);
	    }
	  }
	}