LCS最长公共序列java实现模板

梦里梦外; 2022-05-28 00:53 98阅读 0赞

*  不提供思想 提供了就是制作车轮子.网上太多了没意义

import java.lang.reflect.Array;
    import java.util.Arrays;
    import java.util.Scanner;
    public class Main {
        
    
        public static void main(String[] args) {
    
    
            String a = "abcdef";
            String b = "xb1d2xf3";
    
            int[][] calc = calc(a.toCharArray(), b.toCharArray());
            int flag=Integer.MAX_VALUE;
            //输出序列
    
            for (int i = 1; i < calc[0].length; i++) {
                if(calc[calc.length-1][i]>calc[calc.length-1][i-1]){
                    System.out.println(b.charAt(i-1));
                }
            }
    
        }
    
    
        public static StringBuilder sb= new StringBuilder("");
        //计算最长序列
        //int[][] 封装对象的话 输出序列会不用循环 内部封装链表.由于简单这里不写了 
        public static int[][] calc(char[]a,char b[]){
    
            int flag[][]=new int[a.length+1][b.length+1];
    
    
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < b.length; j++) {
                    if(a[i]==b[j]){ 
                        flag[i+1][j+1]=flag[i][j]+1;
                    }else{
                        flag[i+1][j+1]=Math.max(flag[i][j+1], flag[i+1][j]);
                    }
                }
            }
            return flag;
        }
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，98人围观）

还没有评论，来说两句吧...

相关阅读

相关最长公共子序列（LCS）

最长公共子序列（LCS） problem [leetcode: 1035. 不相交的线][leetcode_ 1035.] > dp\[i\]\[j\]：nums

朴灿烈づ我的快乐病毒、/ 2022年10月14日 13:54/ 0 赞/ 177 阅读

相关最长公共子序列（LCS）

这两天编程涉及到求两个字符串的最长公共子序列问题，于是便重新复习之前一直没弄懂的最长公共子序列算法，也算是弄懂了一点。算法分析：采用动态规划方法来解决问题，将最长公共子

分手后的思念是犯贱/ 2022年09月29日 15:52/ 0 赞/ 178 阅读

相关最长公共子序列LCS问题

好久没有写博客了，刚才在网上看了清华大学的数据结构公开课，链接：https://www.xuetangx.com 可以注册个账号去听数据结构课程，老师讲的特好。我的代码是按

冷不防/ 2022年09月17日 15:21/ 0 赞/ 208 阅读

相关 LCS 最长公共子序列

首先要明白什么是子序列，什么是子串；设：主串长度为n；子序列：从主串中抽出少于n的元素组成的序列（这些抽出的元素比一定是连续的他们的相对位置不变）；

绝地灬酷狼/ 2022年08月03日 14:57/ 0 赞/ 175 阅读

相关最长公共子序列(LCS)问题

> > 程序员编程艺术第十一章：最长公共子序列(LCS)问题 0、前言程序员编程艺术系列重新开始创作了（前十章，请参考[程序员编程艺术第一~十章集锦与总结][Li

你的名字/ 2022年07月12日 03:15/ 0 赞/ 187 阅读

相关最长公共子序列Lcs

1.给出两个字符串A B，求A与B的最长公共子序列的长度（子序列不要求是连续的）。 2.给出两个字符串A B，求A与B的最长公共子序列子串（子序列不要求是连续的）。

浅浅的花香味﹌/ 2022年06月12日 10:55/ 0 赞/ 187 阅读

相关最长公共子序列（LCS）算法

一、最长公共字串与最长公共子序列最长公共子串（Longest Common Substirng）子串是串的一个连续的部分，子串中字符的位置必须连续。例如：有

Love The Way You Lie/ 2022年06月05日 01:10/ 0 赞/ 257 阅读

相关求最长公共子序列（LCS）

题目：求最长公共子序列（LCS）思路：经典的动态规划法， c\[i,j\]表示Xi与Yj的最长公共子序列，其中 Xi = \{x1，、、、xi\}

傷城~/ 2022年05月30日 02:59/ 0 赞/ 199 阅读

相关 LCS/最长公共子序列/最长公共子串实现 Python/Java

参考 [http://blog.csdn.net/u012102306/article/details/53184446][http_blog.csdn.net_u012

阳光穿透心脏的1/2处/ 2022年05月29日 04:40/ 0 赞/ 227 阅读

相关 LCS最长公共序列java实现模板

不提供思想提供了就是制作车轮子.网上太多了没意义 import java.lang.reflect.Array; import java.util.A

梦里梦外;/ 2022年05月28日 00:53/ 0 赞/ 99 阅读