问题：给定两个字符串，求出它们的最长公共子序列的长度。如：a = "xzyzzyx", b = "zxyyzxz"，则其最长公共子序列的长度为4，"zyyx".
注意：最长公共子序列不一定要连续（连续的叫最长公共子串），最长公共子序列也可能不唯一。如上面也可以是："xyyx".
穷举一般都能解决问题，但效率过低（指数时间），这个在密码学上叫计算上不可行。我们可以运用动态规划的思想，可以在多项式时间内解决。
算法基本思路：
1.求最长公共子序列的长度。
给定字符串 a 和 b，可知它们的长度 alen 和 blen。设有二维数组 L[0...alen][0...blen]，L[i][j] 其含义为：i 表示 a 目前的长度即串a0a1..ai-1（若i为0，则表示a为空串），j表示 b 目前长度即串b0b1...bj-1（若j为0，则表示b为空串）。L[i][j] 表示串a0a1..ai-1与串b0b1...bj-1的最长公共子序列的长度。
注意，a 和 b 的下标由0开始，即 i-1（j-1）表示当前字符。
如果 a[i-1] == b[j-1] 即当前字符相等，则 L[i][j] = L[i-1][j-1] + 1 即最长公共子序列长度加1；
如果 a[i-1] != b[j-1] 即当前字符不等，则 L[i][j] = max(L[i-1][j], L[i][j-1]) 即忽略ai-1取最长公共子序列长度与忽略bj-1最长公共子序列长度作比较取较大值；
算法自底向上逐步求解，可以每一步都是当前最优解，结果也是最优解。
2.求最长公共子序列的一个解。
求得最长公共子序列长度后，可以很轻松得到其一个解，只需要运用已有的 L.
从后向前回溯，设 i = alen, j = blen，一直到 i 或 j 为 0（即其中一个串遍历完毕）
如果 a[i-1] == b[j-1]，则保存a[i-1]，然后后退（即 i --, j --）；
否则，查看 L[i][j] 是否和 L[i-1][j] 相等，若相等，则意味着可以抛弃掉 a[i-1]即 i --；若不等，那么 L[i][j] 就会和 L[i][j-1] 相等，则抛弃掉 b[j-1]即 j --。
算法实现：
思路如上。在开始前应该将 L[0][*] 和 L[*][0] 初始化为0，因为空串子序列就是空串。这些作为后续构造最优解的基础。
动态规划在于找到一个最优的递推式，而递推式的存在必须有基础。
注意，我用java来实现这个算法，算法同时返回长度和一个子序列，不熟悉java的人可以忽略那部分代码，不会影响算法的理解。
/*
input: String a, String b
table: int l[0..an][0..bn] //l[i][j] = lcs(a[0..i-1], b[0..j-1])
if a[i-1] == b[j-1]: l[i][j] = l[i-1][j-1] + 1
if a[i-1] != b[j-1]: l[i][j] = max(l[i-1][j], l[i][j-1])
because if a[i-1] == b[j-1], then add a[i-1], len+1;
if a[i-1] != b[j-1], then there are two cases: (1)add a[i-1], then l[i][j-1]
(2)add b[j-1], then l[i-1][j]
get the string:
reverse search l, if a[i-1] == b[j-1], then l[i-1][j-1];
else check l[i-1][j] or l[i][j-1] equals l[i][j]
*/
import java.util.ArrayList;
public class LCS{
public static ArrayList lcs(String a, String b){
int aLen = a.length(), bLen = b.length();
int[][] l = new int[aLen+1][bLen+1];
//if j = 0, then l[i][0] = 0
for(int i = 0; i < aLen; i ++){
l[i][0] = 0;
}
//if i = 0, then l[0][j] = 0
for(int j = 0; j < bLen; j ++){
l[0][j] = 0;
}
//i is the current aLen
//j is the current bLen
for(int i = 1; i <= aLen; i ++){
for(int j = 1; j <= bLen; j ++){
if(a.charAt(i-1) == b.charAt(j-1)){
l[i][j] = l[i-1][j-1] + 1;
}
else{
l[i][j] = Math.max(l[i][j-1], l[i-1][j]);
}
}
}
String result = getLcsString(a, b, l);
ArrayList al = new ArrayList();
al.add(l[aLen][bLen]);
al.add(result);
// for(int i = 0; i < l.length; i ++){
// for(int j = 0; j < l[i].length; j ++){
// System.out.print(l[i][j] + " ");
// }
// System.out.println();
// }
return al;
}
private static String getLcsString(String a, String b, int[][] l){
//build the result string
String result = "";
int i = a.length(), j = b.length();
while(i > 0 && j > 0){
if(a.charAt(i-1) == b.charAt(j-1)){
result = a.charAt(i-1) + result;
i --;
j --;
}
else{
if(l[i][j] == l[i][j-1]){
j --;
}
else{
i --;
}
}
}
return result;
}
public static void main(String[] args) {
//Unit Testing
String a = "xzyzzyx";
String b = "zxyyzxz";
ArrayList al = lcs(a, b);
int len = (int) al.get(0);
String s = (String) al.get(1);
System.out.println(len + " : " + s);
}
}