package test;

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);

		Display(b, x, x.length - 1, y.length - 1);
	}

	/**
	 * @param x
	 * @param y
	 * @return 返回一个记录决定搜索的方向的数组
	 */
	public static int[][] getLength(String[] x, String[] y) {
		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++) {
				// 对应第一个性质
				if (x[i] == y[j]) {
					c[i][j] = c[i - 1][j - 1] + 1;
					b[i][j] = 1;
				}
				// 对应第二或者第三个性质
				else if (c[i - 1][j] >= c[i][j - 1]) {
					c[i][j] = c[i - 1][j];
					b[i][j] = 0;
				}
				// 对应第二或者第三个性质
				else {
					c[i][j] = c[i][j - 1];
					b[i][j] = -1;
				}
			}
		}

		return b;
	}

	// 回溯的基本实现，采取递归的方式
	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);
		}
	}
}