求两个字符串的最长公共子串（字母可以不相邻，但是顺序不变）
不知道为什么笔试总是遇到这些题目，看来经典算法，大家都喜欢啊，这个是LCS问题，动态规划。
问题：求两个字符串的最长公共子串，字母可以不相邻，但是顺序不变
?
代码：
public class lcs {
?public static void LCS_Print(String str1, String str2) {
??int length1 = str1.length();
??int length2 = str2.length();
??int list[][] = new int[length1 + 1][length2 + 1];//初始全为0
??int i;//行
??int j;//列
??// 标记
??for (i = length1 - 1; i >= 0; i--) {
???for (j = length2 - 1; j >= 0; j--) {
????if (str1.charAt(i) == str2.charAt(j)) { //相同
?????list[i][j] = list[i + 1][j + 1] + 1;
????} else {//不同
?????list[i][j] = Math.max(list[i + 1][j], list[i][j + 1]);
????}
???}
??}
??// 计算lcs
??i = 0;
??j = 0;
??while (i < length1 && j < length2) {
???if (str1.charAt(i) == str2.charAt(j)) {//斜着走
????System.out.print(str1.charAt(i));
????i++;
????j++;
???} else if (list[i + 1][j] >= list[i][j + 1]) {//向下走
????i++;
???} else{//向左走
????j++;
???}
??}
??System.out.println();
?}
?public static void main(String[] args) {
??String str1 = "abcddeesdd";
??String str2 = "asadaaddss";
??lcs.LCS_Print(str1, str2);
?}
}
?
