最长公共子序列+元素打印

爱被打了一巴掌 2024-02-18 16:34 10阅读 0赞

代码：

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int maxn = 100+10;
    char a[maxn],b[maxn];
    int dp[maxn][maxn];
    int path[maxn][maxn];
    
    void print(int len1 , int len2){
    	if(len1 < 0 || len2 < 0) return ;
    	if(path[len1][len2] == 1){
    		print(len1-1,len2-1);
    		printf("%c",a[len1]);
    	}else if(path[len1][len2] == 2){
    		print(len1-1,len2);
    	}else {
    		print(len1,len2-1);
    	}
    }
    
    int main(){
    	while(scanf("%s%s",a+1,b+1)== 2){
    		int len1 = strlen(a+1);
    		int len2 = strlen(b+1);
    				
    		for(int i = 0; i <= len2; i++)
    		 dp[0][i] = 0;
    		 
    		for(int i = 1; i <= len1; i++){
    			for(int j = 1; j <= len2; j++){
    				if(a[i] == b[j]){
    					dp[i][j] = dp[i-1][j-1] + 1;
    					path[i][j] = 1;
    				}else {
    					//dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    					if(dp[i-1][j] > dp[i][j-1]){
    						dp[i][j] = dp[i-1][j] ;
    						path[i][j] = 2;
    					}else {
    						dp[i][j] = dp[i][j-1];
    						path[i][j] = 3;
    					}
    				}
    			}
    		} 
    		
    		printf("最长公共子序列的长度为:");
    		printf("%d\n",dp[len1][len2]);
    		printf("最长公共子序列为:");
    		print(len1,len2); //递归打印 
    		printf("\n");
    	}
    	return 0;
    }

![Center][]

[Center]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/ad520cb0706049a8acbff459a7d7a684.png

发表评论取消回复

表情：

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

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

相关阅读

相关最长公共子序列+元素打印

代码： include<cstdio> include<algorithm> include<cstring> using namespace

爱被打了一巴掌/ 2024年02月18日 16:34/ 0 赞/ 11 阅读

相关最长公共子序列

最长公共子序列 1、参考资料 https://leetcode-cn.com/problems/longest-common-subsequence/ 2、题目

阳光穿透心脏的1/2处/ 2022年12月09日 04:57/ 0 赞/ 241 阅读

相关最长公共子序列

include <iostream> include <assert.h> include <string> using namesp

男娘i/ 2022年09月30日 10:00/ 0 赞/ 216 阅读

相关最长公共子序列

最长公共子序列时间限制：3000 ms | 内存限制：65535 KB 难度：3 描述咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列

骑猪看日落/ 2022年09月30日 06:28/ 0 赞/ 219 阅读

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

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

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

相关最长公共子序列

一个序列的子序列是该序列中删除某些元素后得到的序列。给定两个子序列X和Y，求二者的最长公共子序列。例如，X=\{A,B,C,B,D,A,B\}，Y=\{B,D,C,A,B,

超、凢脫俗/ 2022年08月02日 06:53/ 0 赞/ 214 阅读

相关最长公共子序列

最长公共子序列最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的，比如ADE和ABCDE的最长公共子序列是ADE。我们用动态规划的方法来思考

向右看齐/ 2022年06月03日 05:17/ 0 赞/ 217 阅读

相关最长公共子序列

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

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

相关最长公共子序列

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

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

相关最长公共子序列

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

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