文档章节

最长公共子序列

datacube
 datacube
发布于 2016/07/07 11:03
字数 709
阅读 5
收藏 0
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的多少次方
 *
 *
 */

输入图片说明
输入图片说明
输入图片说明
输入图片说明
输入图片说明
输入图片说明 输入图片说明 输入图片说明
输入图片说明
输入图片说明
输入图片说明
输入图片说明
输入图片说明

© 著作权归作者所有

上一篇: 最长公共子串
下一篇: 翻转字符串
datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问

暂无文章

关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
6
0
object 类中有哪些方法?

getClass(): 获取运行时类的对象 equals():判断其他对象是否与此对象相等 hashcode():返回该对象的哈希码值 toString():返回该对象的字符串表示 clone(): 创建并返此对象的一个副本 wait...

happywe
今天
6
0
Docker容器实战(七) - 容器中进程视野下的文件系统

前两文中,讲了Linux容器最基础的两种技术 Namespace 作用是“隔离”,它让应用进程只能看到该Namespace内的“世界” Cgroups 作用是“限制”,它给这个“世界”围上了一圈看不见的墙 这么一...

JavaEdge
今天
8
0
文件访问和共享的方法介绍

在上一篇文章中,你了解到文件有三个不同的权限集。拥有该文件的用户有一个集合,拥有该文件的组的成员有一个集合,然后最终一个集合适用于其他所有人。在长列表(ls -l)中这些权限使用符号...

老孟的Linux私房菜
今天
7
0
面试套路题目

作者:抱紧超越小姐姐 链接:https://www.nowcoder.com/discuss/309292?type=3 来源:牛客网 面试时候的潜台词 抱紧超越小姐姐 编辑于 2019-10-15 16:14:56APP内打开赞 3 | 收藏 4 | 回复24 ...

MtrS
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部