最长公共子序列

题目

 

如果字符串1中的所有字符都按顺序的出现在字符串2中，那么称字符串1是字符串2的子串。现在给定两个字符串，求它们的最长公共子串。

 

例如：对于字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，长度为4。

 

 

思路

 

考虑字符串X = {x1, x2, ... xm} 和 Y = {y1, y2, ... yn}，记 Z = {z1, z2, ... zk} 为 X 和 Y 的任意一个LCS。

 

1. 如果 xm = yn，那么 zk = xm = yn 而且 Zk-1 是 Xm-1 和 Yn-1 的一个LCS。
2. 如果 xm ≠ yn，那么 zk ≠ xm 蕴含 Z 是 Xm-1 和 Y 的一个LCS。
3. 如果 xm ≠ yn，那么 zk ≠ yn 蕴含 Z 是 X 和 Yn-1 的一个LCS。

那么如果要求 X 和 Y 的一个LCS，先看如果 xm = yn，则必须找出 Xm-1 和 Yn-1 的一个LCS。将 xm = yn 添加到这个LCS上；如果 xm ≠ yn，就必须找出 Xm-1 和 Y 的一个LCS 以及 X 和 Yn-1 之间的一个LCS。其中较长的就是 X 和 Y 的一个LCS。则有以下递推式。

 

我们设c[i][j]为 Xi 和 Yj 的一个LCS的长度，那么

 

1. if i < 0 || j < 0，                  c[i][j] = 0;
2. if i, j >= 0 && xi = yj，  c[i][j] = c[i-1][j-1] + 1;
3. if i, j >= 0 && xi ≠ yj，        c[i][j] = max {c[i-1][j], c[i][j-1]};

 

构造一个LCS

 

可以使用b[i][j]来记录构造的方向，0表示由Xi-1和Yj-1构造，1表示由Xi-1和Yj构造，2表示由Xi和Yj-1构造。

 

 

实现

 

 

public class LCS {
	
	private int[][] c;
	private int[][] b;
	
	public void lcs(char[] s1, char[] s2) {
		c = new int[s1.length+1][s2.length+1];
		b = new int[s1.length+1][s2.length+1];
		
		for (int i = 0; i <= s1.length; i++) {
			c[i][0] = 0;
		}
		for (int j = 0; j <= s2.length; j++) {
			c[0][j] = 0;
		}
		
		for (int i = 1; i <= s1.length; i++) {
			for (int j = 1; j <= s2.length; j++) {
				if(s1[i-1] == s2[j-1]) {
					c[i][j] = c[i-1][j-1] + 1;
					b[i][j] = 0;
				} else {
					if (c[i-1][j] >= c[i][j-1]) {
						c[i][j] = c[i-1][j];
						b[i][j] = 1;
					} else {
						c[i][j] = c[i][j-1];
						b[i][j] = 2;
					}
				}
			}
		}
		
		System.out.println("the lcs is: " + c[s1.length][s2.length]);
		printSeq(s1, s1.length, s2.length);
	}
	
	public void printSeq(char[] s1, int i, int j) {
		if (i == 0 || j == 0)
			return;
		if (b[i][j] == 0) {
			printSeq(s1, i-1, j-1);
			System.out.print(s1[i-1] + " ");
		} else if (b[i][j] == 1) {
			printSeq(s1, i-1, j);
		} else {
			printSeq(s1, i, j-1);
		}
	}
	
	public static void main(String[] args) {
		char[] s1 = {'b','d','c','a','b','a'};
		char[] s2 = {'a','b','c','b','d','a','b'};
		LCS l = new LCS();
		l.lcs(s1, s2);
	}
}