//最长公共子序列
 
//最长公共子序列地归解法
package wkx;
 
import java.io.IOException;
 
public class Test { 
	
	private static int LCSLength(char[] A, char[] B, int[][] m, int[][] s,
			int i, int j) {
		if (i < 0 || j < 0)
			return 0;
		if (m[i][j] != 0)
			return m[i][j];
		if (A[i] == B[j]) {
			s[i][j] = 1;
			m[i][j] = LCSLength(A, B, m, s, i - 1, j - 1) + 1;
		} else {
			int a = LCSLength(A, B, m, s, i - 1, j);
			int b = LCSLength(A, B, m, s, i, j - 1);
			if (a > b) {
				s[i][j] = 2;
				m[i][j] = a;
			} else {
				s[i][j] = 3;
				m[i][j] = b;
			}
		}
		return m[i][j];
	}
 
	private static void LCS(char[] A, int[][] s, int i, int j,StringBuffer str) {
		if (i < 0 || j < 0)
			return;
		if (s[i][j] == 1) {
			str.append(A[i]);
			LCS(A, s, i - 1, j - 1,str);
		} else if (s[i][j] == 2) {
			LCS(A, s, i - 1, j,str);
		} else {
			LCS(A, s, i, j - 1,str);
		}
	}
 
	public static void main(String[] args) throws IOException {
		String A = "ASSBDGCGDHDERDFGG";
		String B = "ASBSSCDEF";
		if (A.length() < B.length()) {
			String t = A;
			A = B;
			B = t;
		}
		int[][] m = new int[100][100];
		int[][] s = new int[100][100];
		System.out.println("Total : "
				+ LCSLength(A.toCharArray(), B.toCharArray(), m, s,
						A.length() - 1, B.length() - 1));
		StringBuffer str=new StringBuffer();
		LCS(A.toCharArray(), s, A.length() - 1, B.length() - 1,str);
		System.out.println(str.reverse());
	}
}