找出所有最长公共子序列算法代码

package basic.dp;

/**
 * 动态规划，找出《所有》最长公共子序列
 * 
 * @description LongestCommonSubSequence.java
 * @author Administrator
 * @date 2018/04/17
 * @version
 */

public class LongestCommonSubSequence {
	public static void main（String[] args） {
		String x = “ABCBDAB“;
		String y = “BDCABA“;
		
		int longest = getLCS（x y）;
		//System.out.println（longest）;
	}

	/**
	 * getLCS TODO :得到最长子序列长度，并输出所有最长子序列
	 * 
	 * @param x
	 *            序列x
	 * @param y
	 *            序列y
	 * @return 最长子序列长度
	 * @author zhiman
	 * @date 2018/04/17 下午9:24:18
	 */
	private static int getLCS（String x String y） {
		int xlen = x.length（）;
		int ylen = y.length（）;

		// 此处的棋盘长度要比字符串长度多加1，需要多存储一行0和一列0
		int[][] commonSublen = new int[xlen + 1][ylen + 1];
		// 1代表上 2 代表向左上 3代表向左 4代表上或者左
		int[][] direction = new int[xlen + 1][ylen + 1];
		// 将整个数组commonSublen填充值
		for （int i = 1; i <= xlen; i++） {
			char xi = x.charAt（i - 1）;
			for （int j = 1; j <= ylen; j++） {
				char yj = y.charAt（j - 1）;
				if （xi == yj） {
					commonSublen[i][j] = commonSublen[i - 1][j - 1] + 1;
					// 2 代表向左上
					direction[i][j] = 2;
				} else if （commonSublen[i - 1][j] > commonSublen[i][j - 1]） {
					commonSublen[i][j] = commonSublen[i - 1][j];
					// 1代表上
					direction[i][j] = 1;
				} else if （commonSublen[i - 1][j] < commonSublen[i][j - 1]） {
					commonSublen[i][j] = commonSublen[i][j - 1];
					// 3代表左
					direction[i][j] = 3;
				} else {
					// 如果commonSublen[i - 1][j] == commonSublen[i][j - 1]
					// 向上或者向左不影响结果
					// 4代表上 或者 左
					commonSublen[i][j] = commonSublen[i - 1][j];
					// 1代表上
					direction[i][j] = 4;
				}