LCS（最长公共子序列）

 

 X=<A,B,C,B,D,A,B>

Y=<B,D,C,A,B,A>

那么，<B,C,B,A> 或者 <B,D,A,B>都是LCS.因为，它们都是X的subsequence，也是Y的subsequence。并且，其长度都为4，达到了最大了。而<B,C,A>则是common subsequence,但不是LCS，因为，其长度只有3.

所以，现在的问题是给定X和Y，要你输出LCS的长度为多少。算法复杂度要求是O(mn),m,n分别是字符串X和Y的长度。

即实现函数public static int LCS(String x,String y)；下标从1开始，即x和y的x.charAt(0)，都是无效值。

 

/*
 * X=<A,B,C,B,D,A,B>
Y=<B,D,C,A,B,A>
那么，<B,C,B,A> 或者 <B,D,A,B>都是LCS.因为，它们都是X的subsequence，也是Y的subsequence。并且，其长度都为4，达到了最大了。

而<B,C,A>则是common subsequence,但不是LCS，因为，其长度只有3.

所以，现在的问题是给定X和Y，要你输出LCS的长度为多少。算法复杂度要求是O(mn),m,n分别是字符串X和Y的长度。

即实现函数public static int LCS(String x,String y)；
下标从1开始，即x和y的x.charAt(0)，都是无效值。
 */
public class LongestCommonSequence {
	
	static String X = " " + "ABCBDAB";
	static String Y = " " + "BDCABA";
	
	private static enum CHOICE{
		BOTH, I_LESS,J_LESS
	}
	
	public static void main(String[] args) {
		LCS(X,Y);
	}
	public static int LCS(String x,String y){
		char[] X = x.toCharArray();
		char[] Y = y.toCharArray();
		int M = x.length();
		int N = y.length();
		int[][] L = new int[M][N];
		CHOICE[][] choice = new CHOICE[M][N];
		
		for(int i=0;i<M;i++){
			L[i][0] = 0;
		}
		for(int i=0;i<N;i++){
			L[0][i] = 0;
		}
		
		for(int i=1;i<M;i++){
			for(int j=1;j<N;j++){
				if(x.charAt(i) == y.charAt(j)){
					L[i][j] = L[i-1][j-1] + 1;
					choice[i][j] = CHOICE.BOTH;
				}
				else if(L[i-1][j] > L[i][j-1]){
					L[i][j] = L[i-1][j];
					choice[i][j] = CHOICE.I_LESS;
				}
				else{
					L[i][j] = L[i][j-1];
					choice[i][j] = CHOICE.J_LESS;
				}
				
			}
		}
		
		System.out.println("Print the whole matrix:");
		for(int i=0;i<M;i++){
			for(int j=0;j<N;j++){
				System.out.print(L[i][j] + " ");
			}
			System.out.println();
		}
		
		System.out.println("Print the whole CHOICE matrix:");
		for(int i=0;i<M;i++){
			for(int j=0;j<N;j++){
				System.out.print(choice[i][j] + " ");
			}
			System.out.println();
		}
		
		System.out.println("Print one of the LCS");
		printOut(x,L,choice,M-1,N-1);/*注意是m-1和n-1*/
		return L[M-1][N-1];
	}
	/*像这样逆序输出的，最好就能想到用递归来实现*/
	private static void printOut(
			String x,int[][] L,CHOICE[][] b,int m,int n){
		if(m==0||n==0){
			return ;
		}
		
		if(b[m][n]==CHOICE.BOTH){
			printOut(x,L,b,m-1,n-1);
			System.out.printf("%c", x.charAt(m));
		}
		else if(b[m][n]==CHOICE.I_LESS){
			printOut(x,L,b,m-1,n);
		}
		else{//b[m][n]为CHOICE.J_LESS
			printOut(x,L,b,m,n-1);
		}
	}
}