最长公共子序列LCS

UnixAgain 发布于2019-08-16 14:26 / 2128人阅读

摘要：最长公共子序列动态规划问题，局部最小单元两值是否相等，相等则从对角线上个位置处的数值，继续状态延续不相等则从上下两个过去的位置找值保持延续，在上下两个过去位置中保持着之前的最长子序列。

最长公共子序列

动态规划问题，局部最小单元：两值是否相等，相等则从对角线上个位置处的数值+1，继续状态延续；不相等则从上下两个过去的位置找值保持延续，在上下两个过去位置中保持着之前的最长子序列。

3.对于状态的理解，保持最佳的，或者延续最佳的。

public class LongestCommonSubsequence {
    public static int compute(char[] str1, char[] str2) {
        int substringLength1 = str1.length;
        int substringLength2 = str2.length;
        int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];
        for (int i = substringLength1-1; i >= 0; i--) {
            for (int j = substringLength2-1; j >= 0; j--) {
//                System.out.println(i);
//                System.out.println(j);
//                System.out.println("-*-  ");
                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]);
                }
            }
        }

        return opt[0][0];
    }
    public static int compute(String str1,String str2){
        return compute(str1.toCharArray(),str2.toCharArray());
    }
    public static void main(String[] args){
        String a1="abcd";
        String a2="bcead";
        int l1=compute(a1,a2);
        System.out.println(l1);
    }
}

GPU云服务器云服务器最长公共子序列最长公共子串最长递增子序列 java最长相同子串

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72996.html

javascript 最长公共子序列

摘要：但不是和的最长公共子序列，而序列和也均为和的最长公共子序列，长度为，而和不存在长度大于等于的公共子序列。最长公共子序列给定序列和，从它们的所有公共子序列中选出长度最长的那一个或几个。为和的最长公共子序列长度。最长公共子序列（Longest Common Subsequence LCS）是从给定的两个序列X和Y中取出尽可能多的一部分字符，按照它们在原序列排列的先后次序排列得到。LCS问...

Xufc 2019-08-22 13:52 评论0 收藏0
动态规划法（十）最长公共子序列（LCS）问题

摘要：最长公共子序列问题指的是求解两个序列和的长度最长的公共子序列。当然，可以看出，问题容易出现重叠子问题，这时候，就需要用动态规划法来解决。问题介绍给定一个序列$X=$，另一个序列$Z=$满足如下条件时称为X的子序列：存在一个严格递增的X的下标序列${i_1,i_2,...,i_k}$，对所有的$j=1,2,...,k$满足$x_{i_j}=z_j.$ 给定两个序列$X$和$Y$...

Ashin 2019-08-15 18:17 评论0 收藏0
动态规划法（十）最长公共子序列（LCS）问题

摘要：最长公共子序列问题指的是求解两个序列和的长度最长的公共子序列。当然，可以看出，问题容易出现重叠子问题，这时候，就需要用动态规划法来解决。问题介绍给定一个序列$X=$，另一个序列$Z=$满足如下条件时称为X的子序列：存在一个严格递增的X的下标序列${i_1,i_2,...,i_k}$，对所有的$j=1,2,...,k$满足$x_{i_j}=z_j.$ 给定两个序列$X$和$Y$...

IamDLY 2019-07-30 16:49 评论0 收藏0
算法设计 - LCS 最长公共子序列&&最长公共子串 &&LIS 最

摘要：若且，则是和的最长公共子序列若且，则是和的最长公共子序列。递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算和的最长公共子序列时，可能要计算出和及和的最长公共子序列。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党本章讲解： 1. LCS（最长公共子序列）O(n^2)的时间复杂...

weizx 2019-08-14 12:07 评论0 收藏0
字符串处理文章outline

摘要：遇到问题查查，看看，大神的讲解问问岛胖君下面是我最近整理出来的关于字符串的文章的怎么翻译汇集目录非常希望强化博客的功能，比如分类，置顶。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党最近在看算法和语言，基本属于看知识 --> java实现 --> 整理blog 这个路线。遇到问题查查st...

Karuru 2019-08-14 15:07 评论0 收藏0