文档章节

最长公共子序列

a_xianyu
 a_xianyu
发布于 2017/09/04 16:08
字数 789
阅读 12
收藏 0
点赞 0
评论 0

from: http://acm.nyist.net/JudgeOnline/problem.php?pid=36

描述: 最长公共子序列也称作最长公共子串(不要求连续),英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

输入

    第一行给出一个整数N(0<N<100)表示待测数据组数
    接下来每组数据两行,分别为待测的两组字符串。每个字符串长度不大于1000.

输出

    每组测试数据输出一个整数,表示最长公共子序列长度。每组结果占一行。

样例输入

2
asdf
adfsd
123abc
abc123abc

样例输出

3
6

Solution: 

直接上状态方程

    

贴代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @create 2017-09-04 8:51
 */
public class Main {
    public static int longestCommonSubstring(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return 0;
        }

        int[][] m = new int[s1.length() + 1][s2.length() + 1];
        //初始化边界条件
        for (int i = 0; i <= s1.length(); i++) { //每行第一列置0
            m[i][0] = 0;
        }
        for (int j = 0; j <= s2.length(); j++) { //每列第一行置0
            m[0][j] = 0;
        }

        int result = 0;
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    m[i][j] = m[i - 1][j - 1] + 1;
                } else {
                    m[i][j] = Math.max(m[i - 1][j], m[i][j - 1]);
                }
                result = Math.max(m[i][j], result);
            }
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            System.out.println(longestCommonSubstring(br.readLine(), br.readLine()));
        }
        br.close();
    }
}

    要想把最长的公共字串打印出来,还是贴代码,直接看结果

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @create 2017-09-04 8:51
 */
public class Main {
    public static String s1, s2;

    public static int[][] longestCommonSubstring() {
        if (s1 == null || s2 == null) {
            return null;
        }

        int[][] m = new int[s1.length() + 1][s2.length() + 1];
        //初始化边界条件
        for (int i = 0; i <= s1.length(); i++) { //每行第一列置0
            m[i][0] = 0;
        }
        for (int j = 0; j <= s2.length(); j++) { //每列第一行置0
            m[0][j] = 0;
        }

        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    m[i][j] = m[i - 1][j - 1] + 1;
                } else {
                    m[i][j] = Math.max(m[i - 1][j], m[i][j - 1]);
                }
            }
        }

        return m;
    }

    public static void printLCS(int[][] m, int i, int j) {//打印最长公共子序列
        if (i == 0 || j == 0) {
            return;
        }
//        System.out.println("i=" + i + ", j=" + j);
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            printLCS(m, i - 1, j - 1);
            System.out.print(s1.charAt(i - 1));
        } else if (m[i-1][j] >= m[i][j]){
            printLCS(m, i - 1, j);
        } else {
            printLCS(m, i, j - 1);
        }
    }

    public static void print(int[][] m) {   //打印矩阵
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m[i].length; j++) {
                if (i == 0 && j == 0) {
                    System.out.print("* ");
                } else if (i == 0) {
                    System.out.print(s2.charAt(j - 1) + " ");
                } else if (j == 0) {
                    System.out.print(s1.charAt(i - 1) + " ");
                } else {
                    System.out.print(m[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            s1 = br.readLine();
            s2 = br.readLine();

            int[][] m = longestCommonSubstring();
            print(m);
            printLCS(m, s1.length(), s2.length());
            System.out.println();
        }
        br.close();
    }
}

对于输入

1
asdf
asfsd

可以得到

* a d f s d 
a 1 1 1 1 1 
s 1 1 1 2 2 
d 1 2 2 2 3 
f 1 2 3 3 3 
asd

打印过程如下图

ps: 要想查看打印过程,将printLCS的第一个System.out.println的注释取消,将第二个System.out.print的注释加上

© 著作权归作者所有

共有 人打赏支持
a_xianyu
粉丝 0
博文 36
码字总数 18533
作品 0
哈尔滨
程序员

暂无相关文章

Spring | IOC AOP 注解 简单使用

写在前面的话 很久没更新笔记了,有人会抱怨:小冯啊,你是不是在偷懒啊,没有学习了。老哥,真的冤枉:我觉得我自己很菜,还在努力学习呢,正在学习Vue.js做管理系统呢。即便这样,我还是不...

Wenyi_Feng ⋅ 今天 ⋅ 0

博客迁移到 https://www.jianshu.com/u/aa501451a235

博客迁移到 https://www.jianshu.com/u/aa501451a235 本博客不再更新

为为02 ⋅ 今天 ⋅ 0

win10怎么彻底关闭自动更新

win10自带的更新每天都很多,每一次下载都要占用大量网络,而且安装要等得时间也蛮久的。 工具/原料 Win10 方法/步骤 单击左下角开始菜单点击设置图标进入设置界面 在设置窗口中输入“服务”...

阿K1225 ⋅ 今天 ⋅ 0

Elasticsearch 6.3.0 SQL功能使用案例分享

The best elasticsearch highlevel java rest api-----bboss Elasticsearch 6.3.0 官方新推出的SQL检索插件非常不错,本文一个实际案例来介绍其使用方法。 1.代码中的sql检索 @Testpu...

bboss ⋅ 今天 ⋅ 0

informix数据库在linux中的安装以及用java/c/c++访问

一、安装前准备 安装JDK(略) 到IBM官网上下载informix软件:iif.12.10.FC9DE.linux-x86_64.tar放在某个大家都可以访问的目录比如:/mypkg,并解压到该目录下。 我也放到了百度云和天翼云上...

wangxuwei ⋅ 今天 ⋅ 0

PHP语言系统ZBLOG或许无法重现月光博客的闪耀历史[图]

最近在写博客,希望通过自己努力打造一个优秀的教育类主题博客,名动江湖,但是问题来了,现在写博客还有前途吗?面对强大的自媒体站点围剿,还有信心和可能型吗? 至于程序部分,我选择了P...

原创小博客 ⋅ 今天 ⋅ 0

IntelliJ IDEA 2018.1新特性

工欲善其事必先利其器,如果有一款IDE可以让你更高效地专注于开发以及源码阅读,为什么不试一试? 本文转载自:netty技术内幕 3月27日,jetbrains正式发布期待已久的IntelliJ IDEA 2018.1,再...

Romane ⋅ 今天 ⋅ 0

浅谈设计模式之工厂模式

工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 在工厂模式中,我们在创建对象时不会对客户端暴露创建逻...

佛系程序猿灬 ⋅ 今天 ⋅ 0

Dockerfile基础命令总结

FROM 指定使用的基础base image FROM scratch # 制作base image ,不使用任何基础imageFROM centos # 使用base imageFROM ubuntu:14.04 尽量使用官方的base image,为了安全 LABEL 描述作...

ExtreU ⋅ 昨天 ⋅ 0

存储,对比私有云和公有云的不同

导读 说起公共存储,很难不与后网络公司时代的选择性外包联系起来,但尽管如此,它还是具备着简单和固有的可用性。公共存储的名字听起来也缺乏专有性,很像是把东西直接堆放在那里而不会得到...

问题终结者 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部