最长公共子序列

 

最长公共子序列(动态规划解决)

其中：某个序列的子序列定义为原序列中的0个或多个元素被去掉之后剩下的元素序列。

给定两个序列

X = { x1 , x2 , … , xm }

Y = { y1 , y2 , … , yn }

求X和Y的一个最长公共子序列

举例

X = { a , b , c , b , d , a , b }

Y = { b , d , c , a , b , a }

最长公共子序列为

LSC = { b , c , b , a }

分析：

最长公共子序列问题具有最优子结构性质

设

X = { x1 , … , xm }

Y = { y1 , … , yn }

及它们的最长子序列

Z = { z1 , … , zk }

则

1、若 xm = yn ， 则 zk = xm = yn，且Z[k-1] 是 X[m-1] 和 Y[n-1] 的最长公共子序列

2、若 xm != yn ，且 zk != xm , 则 Z 是 X[m-1] 和 Y 的最长公共子序列

3、若 xm != yn , 且 zk != yn , 则 Z 是 Y[n-1] 和 X 的最长公共子序列

定义c[i,j]为序列Xi和Yj的最长公共子序列的长度，由性质导出子问题的递归结构

当 i = 0 , j = 0 时 , c[i][j] = 0

当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + 1

当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }

 

在这个公式的基础上不难得到一个指数复杂度的递归算法求最长公共子序列，但是考虑到对长度分别为m, n的序列X, Y，其前缀分别有m+1, n+1个，不同的子问题个数的最多有(m+1)(n+1)个，可以用动态规划法自底向上求解。算法是：

对给定的xm , yn

1、如果m=0或者n=0，返回0，算法结束。

2、建立数组c[m+1][n+1]，将c[0][0..n], c[0..m][0]初始化为0。[注：c[i][j]在i=0或j=0时取值为0。]

3、按照从左到右，从上到下的顺序填表。对c[i][j]来说，如果xi=yj，那么令delta=1, c[i][j]的值是以下三者中最大的一个：c[i-1][j], c[i][j-1], c[i-1][j-1]+delta。

4、表c填满后，c[m][n]的值就是最大公共子序列的长度。

5、填表过程结束后，按照第3步的规则倒推，即可知道哪些i, j的值是出现在最长公共子序列中的下标。

 

代码如下:

 

	String mStr1 = "abefcadasda";
	String mStr2 = "abkcefaasd";

	// 公共子序列长度
	int[][] mLength = new int[mStr1.length() + 1][mStr2.length() + 1];
	
	//路径
	String[][] mPath = new String[mStr1.length() + 1][mStr2.length() + 1];

	// 计算最长公共序列的长度以及记录路径
	public void LCS(String s1, String s2) {
		for (int i = 0; i < s1.length(); i++) {
			mLength[i][0] = 0;
		}

		for (int j = 0; j < s2.length(); j++) {
			mLength[0][j] = 0;
		}

		for (int i = 0; i < s1.length(); i++) {
			for (int j = 0; j < s2.length(); j++) {
				// 字符相等，表中数据加1，用“↖”表示从对角线返回
				if (s1.charAt(i) == s2.charAt(j)) {
					mLength[i + 1][j + 1] = mLength[i][j] + 1;
					mPath[i + 1][j + 1] = "↖";
				}
				// 当前两个字符不相等，表中数据继承上方的数据，用“↑”表示向上返回
				else if (mLength[i][j + 1] >= mLength[i + 1][j]) {
					mLength[i + 1][j + 1] = mLength[i][j + 1];
					mPath[i + 1][j + 1] = "↑";
				}
				// 表中数据继承左方的数据，用“←”表示向左返回
				else {
					mLength[i + 1][j + 1] = mLength[i + 1][j];
					mPath[i + 1][j + 1] = "←";
				}
			}
		}
	}// end LCS

	// 输出最长公共序列
	public void print_LCS(String[][] path, String str1, int str1_length, int str2_length) {
		// 其中一个字符串为空，返回
		if (str1_length == -1 || str2_length == -1) {
			return;
		}
		// 对角线返回
		if (path[str1_length + 1][str2_length + 1] == "↖") {
			print_LCS(path, str1, str1_length - 1, str2_length - 1);
			System.out.print(str1.charAt(str1_length));
		}
		// 向上返回
		else if (path[str1_length + 1][str2_length + 1] == "↑") {
			print_LCS(path, str1, str1_length - 1, str2_length);
		}
		// 向左返回
		else
			print_LCS(path, str1, str1_length, str2_length - 1);
	}// end print_LCS

	public static void main(String[] args) {
		LCSProblem lcs = new LCSProblem();
		lcs.LCS(lcs.mStr1, lcs.mStr2);
		lcs.print_LCS(lcs.mPath, lcs.mStr1, lcs.mStr1.length() - 1, lcs.mStr2.length() - 1);
		System.out.print(" length:"+lcs.mLength[lcs.mStr1.length()][lcs.mStr2.length()]);
	}