最长公共子序列

男娘i 2022-09-30 10:00 218阅读 0赞

#include <iostream>
    #include <assert.h>
    #include <string>
    
    using namespace std;
    
    #define Max(a,b) (a)>(b)?(a):(b)
    int main(void)
    {
    	string str1 = "abcdss";
    	string str2 = "asbda";
    
    	int len1 = str1.length();
    	int len2 = str2.length();
    
    	int A[50][50] = { 0 };
    
    	for (int i = 1; i <= len1; i++)
    	{
    		for (int j = 1; j <= len2; j++)
    		{
    			if (str1[i-1] == str2[j-1])
    			{
    				A[i][j] = A[i - 1][j - 1] + 1;
    			}
    			else
    			{
    				A[i][j] = Max(A[i - 1][j], A[i][j - 1]);
    			}
    		}
    	}
    
    	cout << "最长公共子序列元素个数: "<<A[len1][len2]<<endl;
    	cout << "最长公共序列(逆序)" << endl;
    
    	for (int i = len1-1,j = len2-1; i >= 0 && j >= 0; )
    	{
    		if (str1[i] == str2[j])
    		{
    			cout << str1[i];
    			i--; j--;
    		}
    		else
    		{
    			if (A[i][j+1] >= A[i+1][j])
    			{
    				i--;
    			}
    			else
    			{
    				j--;
    			}
    		}
    	}
    
    	return 0;
    }

参考博客： [http://www.cnblogs.com/huangxincheng/archive/2012/11/11/2764625.html][http_www.cnblogs.com_huangxincheng_archive_2012_11_11_2764625.html]

[http_www.cnblogs.com_huangxincheng_archive_2012_11_11_2764625.html]: http://http://www.cnblogs.com/huangxincheng/archive/2012/11/11/2764625.html

发表评论取消回复

表情：

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

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

相关阅读

相关最长公共子序列

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

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

相关最长公共子序列

/ 求两个字符串的最长公共子序列 / public class Solution7 { public static void ma

客官°小女子只卖身不卖艺/ 2022年10月29日 11:17/ 0 赞/ 199 阅读

相关最长公共子序列

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

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

相关最长公共子序列

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

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

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

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

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

相关最长公共子序列

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

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

相关最长公共子序列

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

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

相关最长公共子序列

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

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

相关最长公共子序列

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

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

相关最长公共子序列

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

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