这里我们实现了一个根据动态规划的思想来获取两个字符串的一个最长公共子序列的工具类，代码如下：

/**
 * 获取两个字符串的一个最长公共子序列的工具类
 * @author suibibk@qq.com
 *
 */
public class LCSTUtil {
    public static String getLCS(String x,String y) {
        //1、定义最长公共子序列的长度
        int m = x.length();
        int n = y.length();
        //2、c[i][j]为最长公共子序列的长度，值为二维数组中的值
        int[][] c = new int[m+1][n+1];
        //3、初始化，第一行和第一列都是0
        for (int i = 0; i < m+1; i++) {
            c[i][0]=0;
        }
        for(int i=0;i<n+1;i++) {
            c[0][i]=0;
        }
        /**
        *    最优子结构路径
        * b[i][j]记录使得c[i][j]取最优值的最优子结构
        * b[i][j]=0表示c[i][j]可以取最优子结构，也就是x.chatAt[i-1]这个值属于最长公共子序列中
        * b[i][j]=1表示最优子结构存在c[i-1][j]中，c[i][j]不可以取得最优子结构
        * b[i][j]=2表示最优子结构存在c[i][j-1]中，c[i][j]不可以取得最优子结构
        */
        int[][] b = new int[m+1][n+1];
        //从第一行开始处理，一直处理到最后一行l[i][j]记录的是最长公共子序列的个数
        for(int i=1;i<=m;i++) {
            //每行都比较完每一列
            for (int j = 1; j <=n; j++) {
                //比较值是否相同
                if(x.charAt(i-1)==y.charAt(j-1)) {
                    //如果相同
                    c[i][j]=c[i-1][j-1]+1;
                    //表示x.charAt(i-1)这个为公共子序列的元素
                    b[i][j]=0;
                    //如果不相同，就表明该元素不属于公共子序列
                }else if(c[i-1][j]>=c[i][j-1]) {
                    //这里表明取得最长公共子序列是l[i-1][j]
                    c[i][j]=c[i-1][j];
                    b[i][j]=1;
                }else{
                    //这里表明取得最长公共子序列是l[i][j-1]
                    c[i][j]=c[i][j-1];
                    b[i][j]=2;
                }
            }
        }
        //这里输出c的值
        /*
         * System.out.println("c:"); for(int i=0;i<=m;i++) { //每行都比较完每一列 for (int j = 0;
         * j <=n; j++) { System.out.print(c[i][j]+"\t"); } //换行 System.out.println(); }
         */
        //输出b
        /*
         * System.out.println("b:"); for(int i=0;i<=m;i++) { //每行都比较完每一列 for (int j = 0;
         * j <=n; j++) { System.out.print(b[i][j]+"\t"); } //换行 System.out.println(); }
         */
        //根据计算最优值时得到的信息，构造问题的最优解。
        String result = getResult(b,x,m,n);
        return result;
    }
    /**
     *    根据计算最优值时得到的信息，构造问题的最优解。
     * @param b 递推路径，最优子结构
     * @param x 字符串x
     * @param m x长度
     * @param n y长度
     * @return
     */
    private static String  getResult(int[][] b,String x,int m,int n) {
        //只有值为0才是最长公共子序列的值
        if(m==0||n==0) {
            //终止
            return "";
        }
        if(b[m][n]==0) {
            //这个值属于最长公共子序列，但是先输出之前的值
            String lcs = getResult(b,x,m-1,n-1)+x.charAt(m-1);
            //System.out.printf("%c",x.charAt(m-1));
            return lcs;
        }else if(b[m][n]==1){
            //这个值不属于最长公共子序列
            return getResult(b,x,m-1,n);
        }else {
            return getResult(b,x,m,n-1);
        }
    }
    public static void main(String[] args) {
        String x = "ELGGQBGFIYKKKZXLBLITXUBGIXEVSM";
        String y = "MEUOEOOGWJPPPYDTPRIZWMQBFWPVRX";
        String result = getLCS(x, y);
        System.out.printf("%s与%s的最长公共子序列为：%s",x,y,result);
    }
}

时间复杂度为O(m+n)可以接受！