public class LongestCommonSubsequence3 {    public static void main(String[] args) {        LongestCommonSubsequence3 lcs = new LongestCommonSubsequence3();        System.out.println(lcs.compute("ABCBDAB","BDCABA"));    }    public static int compute(char[] str1, char[] str2)    {        int substringLength1 = str1.length;        int substringLength2 = str2.length;        // 构造二维数组记录子问题A[i]和B[j]的LCS的长度,默认初始化为0        int[][] chess = new int[substringLength1 + 1][substringLength2 + 1];        // 从从前到后，动态规划计算所有子问题。也可从前向后        for (int i = 1; i <= substringLength1; i++)        {            for (int j = 1; j <= substringLength2; j++)            {                if (str1[i - 1] == str2[j - 1])                    chess[i][j] = chess[i - 1][j - 1] + 1;// 状态转移方程                else                    chess[i][j] = Math.max(chess[i - 1][j], chess[i][j - 1]);// 状态转移方程            }        }        System.out.println("substring1:" + new String(str1));        System.out.println("substring2:" + new String(str2));        System.out.print("LCS:");        int i = str1.length, j = str2.length;        String temp = "";        while (i != 0 && j != 0)        {            if (str1[i - 1] == str2[j - 1])            {                temp += str1[i - 1];                i--;                j--;            }            else{                if (chess[i][j - 1] > chess[i - 1][j])                    j--;                else                    i--;            }        }        for (int k = temp.length() - 1; k >= 0; k--) {            System.out.print(temp.toCharArray()[k]);        }        System.out.println();        return chess[str1.length][str2.length];    }    public int compute(String str1, String str2)    {        return compute(str1.toCharArray(), str2.toCharArray());    }}//================public class LongestCommonSubsequence2 {    public static void main(String[] args) {        LongestCommonSubsequence2 lcs = new LongestCommonSubsequence2();        System.out.println(lcs.compute("ABCBDAB","BDCABA"));    }    public static int compute(char[] str1, char[] str2)    {        int substringLength1 = str1.length;        int substringLength2 = str2.length;        // 构造二维数组记录子问题A[i]和B[j]的LCS的长度        int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];        // 从后向前，动态规划计算所有子问题。也可从前到后。        for (int i = substringLength1 - 1; i >= 0; i--)        {            for (int j = substringLength2 - 1; j >= 0; j--)            {                if (str1[i] == str2[j])                    opt[i][j] = opt[i + 1][j + 1] + 1;// 状态转移方程                else                    opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);// 状态转移方程            }        }        System.out.println("substring1:" + new String(str1));        System.out.println("substring2:" + new String(str2));        System.out.print("LCS:");        int i = 0, j = 0;        while (i < substringLength1 && j < substringLength2)        {            if (str1[i] == str2[j])            {                System.out.print(str1[i]);                i++;                j++;            }            else if (opt[i + 1][j] >= opt[i][j + 1])                i++;            else                j++;        }        System.out.println();        return opt[0][0];    }    public int compute(String str1, String str2)    {        return compute(str1.toCharArray(), str2.toCharArray());    }}//====================package com.lifeibigdata.algorithms.string;/** * Created by lifei on 16/5/25. */public class LongestCommonSubsequence {    public static void main(String[] args) {        char[] x = {' ','A','B','C','B','D','A','B'};        char[] y = {' ','B','D','C','A','B','A'};        LongestCommonSubsequence lcs = new LongestCommonSubsequence();        lcs.printLCS(lcs.lcsLength(x, y), x, x.length-1, y.length-1);    }    void printLCS(int[][] b,char[] x,int i,int j){        if(i == 0 || j == 0)            return;        if(b[i][j] == 1){            printLCS(b,x,i - 1,j - 1);            System.out.print(x[i] + "\t");        }else if(b[i][j] == 2)            printLCS(b,x,i - 1,j);        else            printLCS(b,x,i,j - 1);    }    int[][] lcsLength(char[] x,char[] y){        int m = x.length;        int n = y.length;        int i,j;        int[][] c = new int[m][n];        int[][] b = new int[m][n];        for(i = 1;i < m;i++)            c[i][0] = 0;        for(j = 0;j < n;j++)            c[0][j] = 0;        for(i = 1;i < m;i++)            for(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;                }            }        return b;    }}/** * 滚动数组只求大小,可以降低空间复杂度,时间复杂度不变 * 求全部的lcs，使用深搜或广搜         * 求有几个lcs，即只求lcs数目，计算有多少分支，即2的多少次方 * * */