求两个字符串的最长公共子串（字母可以不相邻，但是顺序不变）

不知道为什么笔试总是遇到这些题目，看来经典算法，大家都喜欢啊，这个是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);
 }

}