首页 > 其他分享 >7-3 最长公共子序列

7-3 最长公共子序列

时间:2023-12-23 22:45:27浏览次数:44  
标签:int s2 s1 公共 序列 最长 dp

7-3 最长公共子序列

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=<x1,x2,…,xm>,则另一序列Z=<z1,z2,…,zk>是X的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik>,使得对于所有j=1,2,…,k有:

Xij=Zj
例如,序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>,则序列<B,C,A>是X和Y的一个公共子序列,序列 <B,C,B,A>也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列.因为X和Y没有长度大于4的公共子序列。

给定两个序列X=<x1,x2,…,xm>和Y=<y1,y2….yn>.要求找出X和Y的一个最长公共子序列。

输入格式:

共有两行。每行为一个由大写字母构成的长度不超过1000的字符串,表示序列X和Y。

输出格式:

第一行为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列.则输出文件仅有一行输出一个整数0。

输入样例:

ADCBDAB
BDCABC

输出样例:

4

简化版代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

char s1[N], s2[N];
int dp[N][N], i, j;

int main()
{
    scanf("%s%s", s1 + 1, s2 + 1);
    for (i = 1; s1[i]; ++i) {
        for (j = 1; s2[j]; ++j) {
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            if (s1[i] != s2[j]) continue;
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }
    printf("%d\n", dp[i - 1][j - 1]);
  
    return 0;
}

中文注释版代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

char s1[N], s2[N];
int dp[N][N], i, j;

int main()
{
    scanf("%s%s", s1 + 1, s2 + 1);

    // 动态规划求解最长公共子序列
    for (i = 1; s1[i]; ++i) {
        for (j = 1; s2[j]; ++j) {
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

            // 如果当前字符相等,更新最长公共子序列长度
            if (s1[i] != s2[j]) continue;
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }

    // 输出最长公共子序列的长度
    printf("%d\n", dp[i - 1][j - 1]);
  
    return 0;
}

java版代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入两个字符串
        String s1 = scanner.next();
        String s2 = scanner.next();

        // 动态规划数组,dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子序列长度
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];

        // 动态规划求解最长公共子序列
        for (int i = 1; i <= s1.length(); ++i) {
            for (int j = 1; j <= s2.length(); ++j) {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);

                // 如果当前字符相等,更新最长公共子序列长度
                if (s1.charAt(i - 1) != s2.charAt(j - 1)) continue;
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }

        // 输出最长公共子序列的长度
        System.out.println(dp[s1.length()][s2.length()]);
    }
}

标签:int,s2,s1,公共,序列,最长,dp
From: https://www.cnblogs.com/aslwr/p/73-the-longest-public-subsequent-sequence-9fnku.html

相关文章

  • 最大公共子图(MCS)的大小、子图编辑距离和嵌入距离
    最大公共子图(MCS)的大小、子图编辑距离和嵌入距离是图匹配和图相似性度量中的常见概念,它们用于比较两个图之间的相似性。以下是它们的定义:最大公共子图(MCS)的大小:定义:最大公共子图是两个图中具有相同结构的最大子图。即,在两个图中找到一个共同的子图,使得这个子图不能再扩展,即......
  • Jmeter:定义公共变量
    一前言环境:window10Jmeter5.3在jmeter中诸如一些协议名称、域名或其它会多次重复输入的值,我们可以定义一些变量来关联这些值,在需要输入的地方输入变量名称jmeter就会识别出变量所指代的具体值二例子在jmeter中定义公共变量常用的有2个地方,一个是testplan,一个是userdefi......
  • 316完全二叉树的公共父结点
    题目:完全二叉树的公共父结点问题描述有一棵无限大的完全二叉树,该二叉树自上而下、自左而右从1开始编号。从某一个结点到根结点(编号是1的结点)都有一条唯一的路径,比如从5到根结点的路径是(5,2,1),从4到根结点的路径是(4,2,1),从根结点1到根结点的路径上只包含一个结点1,因此路径就是(1......
  • python 最长公共前缀 5种解法
    解法一:水平扫描这是最简单的一种方法,逐个字符比较每个字符串的相应位置,直到遇到不匹配的字符为止。deflongest_common_prefix(strs):ifnotstrs:return""prefix=strs[0]foriinrange(1,len(strs)):whilestrs[i].find(prefix)!=0:......
  • R语言经济学:动态模型平均(DMA)、动态模型选择(DMS)预测原油价格时间序列
    原文链接:http://tecdat.cn/?p=22458 原文出处:拓端数据部落公众号 简介本文提供了一个经济案例。着重于原油市场的例子。简要地提供了在经济学中使用模型平均和贝叶斯方法的论据,使用了动态模型平均法(DMA),并与ARIMA、TVP等方法进行比较。希望对经济和金融领域的从业人员和研究......
  • 『LeetCode』3. 无重复字符的最长子串 Longest Substring Without Repeating Characte
    『1』双指针算法我的想法:一般看到字符串子串问题想到用双指针解,看到字符串子序列问题想到用动态规划解。此题用双指针可以很快解题。遍历字符串中的每个字符s.charAt[i],对于每一个i,找到j使得双指针[j,i]维护的是以s.charAt[i]结尾的无重复字符的最长子串,长度为i-j+1,......
  • 1-4时间序列数据建模流程范例
    0.配置importtorchprint('torch.__version__=',torch.__version__)"""torch.__version__=2.1.0+cpu"""importos#mac系统上pytorch和matplotlib在jupyter中同时跑需要更改环境变量#os.environ["KMP_DUPLICATE_LIB_OK"]=&q......
  • 梭梭带你彻底搞懂YAML序列化语言
    目录前言简介yaml基本语法规则yaml支持的数据结构有三种基本语法大小写敏感用缩进表示层级关系用#表示注释一个文件中可以包含多个文件的内容数据结构与类型对象(Mapping)数组(Sequence)标量(Scalars)字符串(String)布尔值(Boolean)整数(Integer)浮点数(FloatingPoint)空(Null)时间戳(Timestamp)......
  • 序列操作
    这道题目非常有助于提高我们对lazy的理解我们设lazy为0表示全部改成0,为1表示全部改成1,为2表示翻转一次,为-1表示没有操作按照我们对lazy的理解,一个节点真实的信息,等价于这个节点到根节点的路径上的节点的lazy的某个“和”操作那么在这道题目的“和”操作,就是深度从深到浅节点的l......
  • dfr之序列化常用字段、soruce、定制返回字段、多表关联反序列化、ModelSerializer的使
    一、序列化类常用字段#除了CharField以外,还要很多别的---》表模型中models.CharField--->基本一一对应#如果跟表模型中对不上:你统一用CharField#重要:(后面说)ListFieldDictField字段字段构造方式BooleanFieldBooleanField()NullBooleanFieldNullB......