1,解决:一个简单的动态规划:
string a,b;
dp[0][_] = dp[_][0] = 0;
dp[i][j] = a[i]==b[j]? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);
2,实例代码:
#include<iostream>
using namespace std;
const int N=100;
int dp[N][N];
//该函数只是得到最大公共长度
int maxSubSquence(const char* a,const char* b)
{
memset(dp,0,sizeof(dp));
int m=strlen(a);
int n=strlen(b);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(a[i-1]==b[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
}
else
dp[i][j]=dp[i-1][j]>dp[i][j-1]? dp[i-1][j]:dp[i][j-1];
}
return dp[m][n];
}
//可以将最长序列返回
char re[N];
int maxSubSquence2(const char* a,const char* b)
{
int s[N][N];
memset(dp,0,sizeof(dp));
int m=strlen(a);
int n=strlen(b);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(a[i-1]==b[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
s[i][j]=1;
}
else
dp[i][j]=dp[i-1][j]>dp[i][j-1]? (s[i][j]=2,dp[i-1][j]):(s[i][j]=3,dp[i][j-1]);
}
int len=dp[m][n];
re[len]='\0';
//根据s[i][j]的状态提取公共子序列
for(int i=m,j=n;i>0&&j>0;)
{
switch(s[i][j])
{
case 1:
re[--len]=a[i-1];i--;j--;
break;
case 2:
i--;
break;
case 3:
j--;
break;
}
}
return dp[m][n];
}
int main()
{
const char* a="xyxzyxyzzy";
const char* b="xzyzxyzxyzxy";
cout<<maxSubSquence2(a,b)<<endl;
cout<<re<<endl;
return 0;
}
分享到:
相关推荐
最长公共子序列算法 本文将详细介绍最长公共子序列(Longest Common Subsequence,LCS)算法的概念、原理和实现。LCS 是一种经典的字符串处理算法,广泛应用于自然语言处理、数据压缩、生物信息学等领域。 什么是...
LCS算法的目标是找到两个字符串的最长公共子序列。其基本思想是构建一个二维数组,其中的每个元素代表对应位置的两个字符是否构成公共子序列。通过遍历这个二维数组,我们可以逐步推导出最长公共子序列。 具体步骤...
在计算机科学领域,字符串处理是常见的一类任务,其中计算两个字符串的相似度以及找到它们的最长公共子序列(Longest Common Subsequence, LCS)是一个经典的问题。本篇将深入探讨这个问题,以及如何使用Java来解决...
递归解法的基本思路是定义一个函数,该函数接收两个字符串作为参数,返回它们的LCS长度。递归关系可以这样描述:如果两个字符串为空,那么它们的LCS长度为0;如果其中一个字符串为空,另一个非空,则LCS长度等于非空...
### C++实现最长公共子序列算法详解 在深入解析给定代码之前,我们先来了解一下“最长公共子序列”(Longest Common Subsequence,简称LCS)的基本概念及其在计算机科学中的应用。LCS问题是一种典型的动态规划问题...
给定两个字符串 text1 和 text2,找到这两个字符串的最长公共子序列(LCS)的长度。一个字符串的子序列是指这样一个字符串:它通过删除原字符串中的某些(也可以不删除)字符而不改变剩余字符的相对顺序得到。 示例...
这里,我们用`L(m,n)`表示两个字符串`X`和`Y`的前`m`个字符与前`n`个字符的最长公共子序列的长度。 算法分析分为以下三个情况: 1. 如果`xm=yn`,即两个字符串在当前位置的字符相等,那么`zk`可以设置为`xm=yn`,...
最长公共子序列(Longest Common Subsequence, LCS)是计算机科学中一种经典的字符串问题,它在比较两个或多个序列时寻找它们之间的最长相同部分,但这个相同部分不需要连续。这个问题在许多领域都有应用,比如生物...
利用指针来查询两个字符串的最长公共子序列,并输出的算法。
【Python求两个字符串最长公共子序列】 在编程领域,字符串操作是常见任务之一,而寻找两个字符串的最长公共子序列(LCS)是其中的一个经典问题。LCS是指两个字符串中都出现过的最长的连续子序列,但不考虑字符在...
- 函数`LCS`接受两个字符串参数,并返回它们的最长公共子串。 - 初始化变量`lenLeft`和`lenRight`分别存储输入字符串的长度。 - 创建字符数组`c`用于记录最长公共子串的长度。 - 遍历`left`字符串中的每个字符,对于...
Problem Description 给你一个序列X和另一个序列Z,当Z中的所有元素都在X中...对于每组输入,输出两个字符串的最长公共子序列的长度。 Sample Input abcfbc abfcab programming contest abcd mnp Sample Output 4 2 0
### 最长公共子序列(LCS):深入解析与实现 #### 一、概念与应用场景 最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一个重要的算法问题,它主要应用于字符串比较、文本编辑、生物信息学...
总结来说,最长公共子序列问题是一个典型的动态规划问题,通过使用C#编程语言,我们可以有效地求解两个字符串的最长公共子序列。这种算法在文本比较、生物信息学、软件工程等领域有广泛应用。理解并能实现这种算法...
哈工大算法实验二,最长公共子序列问题,动态规划解决LCS ...3.实现三个字符串最长公共子序列的动态规划算法 4.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析了算法的性能
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的问题,主要应用于比较和分析两个或多个序列的相似性。在这个问题中,目标是找到两个序列的最长子序列,这个子序列不需要在原序列中...
算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA