最长公共子序列问题

川长思鸟来 2022-02-16 02:30 186阅读 0赞

### [参考：https://blog.csdn.net/huanghanqian/article/details/78892808][https_blog.csdn.net_huanghanqian_article_details_78892808] ###

### 最长公共子序列问题 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定两个序列 X=\{x1,x2,…,xm\} 和 Y=\{y1,y2,…,yn\}，找出X和Y的最长公共子序列。

Input

输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。

Output

每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。

Sample Input

ABCBDAB
    BDCABA

Sample Output

4

#include <iostream>  
    #include<string>
    using namespace std;
    int dp[1001][1001] = {0};
    
    int max(int a, int b) {
    	return a > b ? a : b;
    }
    int main() {
    	string a, b;
    	while (cin >> a >> b) {
    		for (int i = 1; i <= a.length(); i++) {
    			for (int j = 1; j <= b.length(); j++) {
    				if (a[i - 1] == b[j - 1]) {
    					dp[i][j] = dp[i - 1][j - 1] + 1;
    				}
    				else {
    					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    				}
    			}
    		}
    		cout << dp[a.length()][b.length()] << endl;
    	}
    	
    	return 0;
    }

[https_blog.csdn.net_huanghanqian_article_details_78892808]: https://blog.csdn.net/huanghanqian/article/details/78892808

发表评论取消回复

表情：

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

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

相关阅读

相关最长公共子序列空间优化最长公共子序列

import java.util.Scanner; / HDU 1159 @author ashzheng 201

ゞ浴缸里的玫瑰/ 2022年08月21日 05:46/ 0 赞/ 263 阅读

相关最长公共子序列问题

Problem Description 给定两个序列X= Input 输入数据有多组，每组有两行，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,

太过爱你忘了你带给我的痛/ 2022年07月12日 03:16/ 0 赞/ 142 阅读

相关最长公共子序列问题

Problem Description 给定两个序列X= Input 输入数据有多组，每组有两行，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,

蔚落/ 2022年07月12日 03:16/ 0 赞/ 139 阅读

相关最长公共子序列问题

Problem Description 给定两个序列 X=\{x1,x2,…,xm\} 和 Y=\{y1,y2,…,yn\}，找出X和Y的最长公共子序列。 Input

你的名字/ 2022年05月16日 01:40/ 0 赞/ 146 阅读

相关最长公共子序列

最长公共子序列问题，具有最优子结构性质设序列Xm=\{x1,x2,…,xm\}和Yn=\{y1,y2,…,yn\}的最长公共子序列为Zk=\{z1

港控/mmm°/ 2022年04月23日 07:04/ 0 赞/ 256 阅读

相关最长公共子序列问题

最长公共子序列问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Prob

向右看齐/ 2022年02月25日 07:07/ 0 赞/ 183 阅读

相关最长公共子序列问题

最长公共子序列问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给定两个序列 X=

我就是我/ 2022年02月17日 12:17/ 0 赞/ 177 阅读

相关最长公共子序列问题

[参考：https://blog.csdn.net/huanghanqian/article/details/78892808][https_blog.csdn.net_hu

川长思鸟来/ 2022年02月16日 02:30/ 0 赞/ 187 阅读

相关最长公共子序列

找出两个字符串的最长公共子序列。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

r囧r小猫/ 2021年11月09日 17:10/ 0 赞/ 389 阅读

相关最长公共子序列

最长公共子序列设X=<x1,x2,x3,x4…,xm>，Y=<y1,y2,y3,y4…,yn>为两个序列，Z=<z1,z2,z3,z4…,zk>是他们的任意公共子序列

迈不过友情╰/ 2021年10月19日 05:48/ 0 赞/ 368 阅读