最长公共子序列和最长公共子串

这篇具有很好参考价值的文章主要介绍了最长公共子序列和最长公共子串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最长公共子序列

题目描述

给出1,2,…,n 的两个排列P1 和 P2 ,求它们的最长公共子序列。

输入格式

第一行是一个数 n

接下来两行,每行为 n 个数,为自然数1,2,…,n 的一个排列。

输出格式

一个数,即最长公共子序列的长度。

题目分析

第一阶段定义dp数组

(1)考虑规模。两个序列的长度就是规模,因为是两个,所以需要两个维度来表示。

(2)考虑限制。这里的限制就是对应位置相等,可以在递推的时候进行限制。

(3)写dp数组。 d p [ i ] [ j ] dp[i][j] dp[i][j]表示的第一个序列前i个值和第二个序列前j个值对应的最长公共子序列

第二阶段推导状态转移方程

(1)如果 s 1 [ i ] = = s 2 [ j ] , d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 s1[i]==s2[j],dp[i][j]=dp[i-1][j-1]+1 s1[i]==s2[j]dp[i][j]=dp[i1][j1]+1

(1)如果 s 1 [ i ] ! = s 2 [ j ] s1[i]!=s2[j] s1[i]!=s2[j],那么我们就要从前一个状态的最大值里面转移过来,前一个状态有哪些呢? d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] dp[i-1][j],dp[i][j-1] dp[i1][j],dp[i][j1]就是它的前一个状态, d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i1][j1]不是,因为他距离 d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i1][j1]已经变化了2步。 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j]=max(dp[i-1][j],dp[i][j-1]) dp[i][j]=max(dp[i1][j],dp[i][j1])

第三阶段写代码

(1)初始化。一开始长度是0。

(2)第一层for循环遍历规模,这里规模是两个维度表示的,所以也需要两层for循环。

(3)第二层for循环仍然遍历规模。

题目代码
import java.io.IOException;
import java.util.Scanner;

public class Main{
public static void main(String[] args) throws NumberFormatException, IOException {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	int m=n;
	int a[] = new int[n+1];
	int b[] = new int[m+1];
	int dp[][] = new int[n+1][m+1];
	for(int i = 1;i <= n;i++) 
		a[i] = scanner.nextInt();
	for(int i = 1;i <= m;i++) 
		b[i] = scanner.nextInt();
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m;j++) {
			if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
		}
	}
	System.out.println(dp[n][m]);
}
}

在洛谷提交还是内存超限,离谱。

最长公共子串

题目分析

注意子串和子序列的差别,abcde中acd是一个子序列,但不是一个子串,abc是一个子串也是一个子序列。子串的要求要比子序列高。子串必须是连续的。那么这一点体现在哪里呢。体现在状态转移方程以及答案上。

第一阶段定义dp数组

(1)考虑规模。两个序列的长度就是规模,因为是两个,所以需要两个维度来表示。

(2)考虑限制。这里的限制就是对应位置相等,可以在递推的时候进行限制。

(3)写dp数组。 d p [ i ] [ j ] dp[i][j] dp[i][j]表示的第一个序列前i个值和第二个序列前j个值对应的最长公共子串

第二阶段推导状态转移方程

(1)如果 s 1 [ i ] = = s 2 [ j ] , d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 s1[i]==s2[j],dp[i][j]=dp[i-1][j-1]+1 s1[i]==s2[j]dp[i][j]=dp[i1][j1]+1

(1)如果 s 1 [ i ] ! = s 2 [ j ] , d p [ i ] [ j ] = 0 s1[i]!=s2[j],dp[i][j]=0 s1[i]!=s2[j]dp[i][j]=0

第三阶段写代码

(1)初始化。一开始长度是0。

(2)第一层for循环遍历规模,这里规模是两个维度表示的,所以也需要两层for循环。

(3)第二层for循环仍然遍历规模。

(4)答案。这里的 d p [ i ] [ j ] dp[i][j] dp[i][j]不一定是最终答案,答案要在过程中记录一个最大值。也就是所有dp值的最大值。 m a x ( d p [ i ] [ j ] ) max(dp[i][j]) max(dp[i][j])文章来源地址https://www.toymoban.com/news/detail-825112.html

题目代码
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Main{
public static void main(String[] args) throws NumberFormatException, IOException {
	Scanner scanner = new Scanner(System.in);
	char a[];
	char b[];
	a = (" "+scanner.next()).toCharArray();
	b = (" "+scanner.next()).toCharArray();
	int n = a.length-1;
	int m = b.length-1;
	int dp[][] = new int[n+1][m+1];	
	int ans = 0;
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m;j++) {
			if(('0'<=a[i]&&a[i]<='9') || ('0'<=b[j]&&b[j]<='9')) continue;
			if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j] = 0;
			ans = Math.max(ans, dp[i][j]);
		}
	}
	System.out.println(ans);
}
}

到了这里,关于最长公共子序列和最长公共子串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法(四·三):动态规划思想——最长公共子序列问题】

    最长公共子序列(Longest Common Subsequence,简称LCS)问题是一种常见的字符串处理问题。它的**目标是找到两个或多个字符串中的最长公共子序列,这个子序列不需要是连续的,但字符在原始字符串中的相对顺序必须保持一致。**例如,考虑两个字符串\\\"ABCD\\\"和\\\"ACDF\\\",它们的最长公

    2024年04月13日
    浏览(50)
  • 【算法】力扣【动态规划,LCS】1143. 最长公共子序列

    1143. 最长公共子序列 本文是对 LCS 这一 动态规划 模型的整理,以力扣平台上的算法题1143:最长公共子序列为模板题进行解析。 该题目要求计算两个字符串的最长公共子序列(Longest Common Subsequence,简称LCS)的长度。字符串的子序列是指在不改变字符顺序的情况下,通过删去

    2024年01月17日
    浏览(61)
  • 最长公共子串(动态规划)

    查找两个字符串a,b中的最长公共子串_牛客题霸_牛客网 1.找a 和 b 的最长公共子串实际上是在a的子串和b的子串中找最长公共子串 ins[i][j]实际上记录的就是 以a的第i个字符和以b的第j个字符结尾的子串中存在的最长公共子串的长度 接下来我们举个例子: a: abcabcde b: abcd ins[1][1]

    2023年04月12日
    浏览(49)
  • python数据结构与算法-动态规划(最长公共子序列)

    一个序列的子序列是在该序列中删去若干元素后得 到的序列。 例如:\\\"ABCD”和“BDF”都是“ABCDEFG”的子序列。 最长公共子序列(LCS) 问题: 给定两个序列X和Y,求X和Y长度最大的公共子字列。 例:X=\\\"ABBCBDE”Y=\\\"DBBCDB”LCS(XY)=\\\"BBCD\\\" 应用场景:字符串相似度比对 (1)问题思考 思考: 暴

    2024年02月08日
    浏览(52)
  • 算法分析:C语言实现动态规划之最长公共子序列

    最长公共子序列问题:          下面的简单问题说明了动态规划的基本原理。在字母表一∑上,分别给出两个长度为n和m的字符串A和B,确定在A和B中最长公共子序列的长度。这里,A = a₁a₂...an。的子序列是一个形式为a₁ka₂k...aik的字符串,其中每个i都在1和n之间,并且

    2023年04月21日
    浏览(37)
  • 算法套路十五——动态规划求解最长公共子序列LCS

    给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

    2024年02月04日
    浏览(52)
  • 算法分析 | 动态规划算法设计之最长公共子序列 C语言版

    声明:凡代码问题,欢迎在评论区沟通。承蒙指正,一起成长! 目录 一、实验内容与要求  二、概要设计 三、直接上代码      四、输入数据及运行结果   内容:最长公共子序列 ·若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序

    2024年02月02日
    浏览(51)
  • 9.动态规划——4.最长公共子序列(动态规划类的算法题该如何解决?)

    设最长公共子序列 d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] 是 S 1 S_1 S 1 ​ 的前 i i i 个元素,是 S 2 S_2 S 2 ​ 的前 j j j 个元素,那么有: 若 S 1 [ i − 1 ] = = S 2 [ i − 1 ] S_1[i-1]==S_2[i-1] S 1 ​ [ i − 1 ] == S 2 ​ [ i − 1 ] ,那么 d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j]=dp[i-1][j-1]+1 d p [

    2024年04月11日
    浏览(47)
  • 【算法训练-字符串 三】最长公共子串、最长公共子序列

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【】,使用【】这个基本的数据结构来实现,这个高频题的站点是: CodeTop ,筛选条件为: 目标公司+最近一年+出现频率排序 ,由高到低的去 牛客TOP101 去找,只有两个地方都出现过才做

    2024年02月09日
    浏览(39)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包