最长公子序列的求解--自底向上求最长公共子串

package 动态规划;

public class 自底向上求最长公共子串 {

public static int lcsLength(char[] x,char[] y,int[][] b) { int m = x.length -1; int n = y.length -1; int[][] c = new int [m+1][n+1]; for(int i = 0; i <= m; i++) c[i][0] = 0; for(int i = 0; i <= n; i++) c[0][i] = 0; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(x[i] == y[j]) { c[i][j] = c[i-1][j-1] +1; b[i][j] = 1; } else if(c[i-1][j] >= c[i][j-1]) { c[i][j] = c[i-1][j]; b[i][j] = 2; } else { c[i][j] = c[i][j-1]; b[i][j] = 3; } } } lcs(m,n,x,b); System.out.println(); System.out.println("最大长度是："); return c[m][n]; } public static void lcs(int i, int j, char[] x,int[][] b) { if(i == 0 || j == 0) return; if(b[i][j] == 1) { lcs(i-1,j-1,x,b); System.out.print(x[i]); } else if(b[i][j] == 2) { lcs(i-1,j,x,b); } else lcs(i,j-1,x,b); } public static void main(String[] args) { String s1 = "ABCBDAB"; char[] c1 = new char[s1.length() + 1];//带0号字符的字符数组 char[] t1 = s1.toCharArray(); //toCharArray() 方法将字符串转换为字符数组 c1[0] = (char)0; for(int i = 0; i < t1.length; i++) { c1[i + 1] = t1[i]; } String s2 = "BDCABA"; char[] c2 = new char[s2.length() + 1];//带0号字符的字符数组 char[] t2 = s2.toCharArray(); c2[0] = (char)0; for(int i = 0; i < t2.length; i++) { c2[i + 1] = t2[i]; } int[][] bak = new int[c1.length][c2.length]; System.out.println("子串为："); System.out.println(lcsLength(c1,c2,bak)); }

}

基本推演过程如下： 得到子串需要用回溯法，应满足条件：x[i] ==y[j] ，就可找到结果，以下仅是一部分结果。 需要做出更多努力的是优化以上程序使其可以找到多条最长公共子串。