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;
}
分享到:
相关推荐
求两个字符串的最长公共子序列.pdf
给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB。则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二、算法求解 这是一个...
利用指针来查询两个字符串的最长公共子序列,并输出的算法。
第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据占1行,它由2个给定序列的字符串组成,两个字符串之间用空格隔开. Output 你的输出应该有C行,即每组测试数据的输出占一行,它是计算出的...
Problem Description 给你一个序列X和另一个序列Z,当Z中的所有元素都在X中...对于每组输入,输出两个字符串的最长公共子序列的长度。 Sample Input abcfbc abfcab programming contest abcd mnp Sample Output 4 2 0
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
哈工大算法实验二,最长公共子序列问题,动态规划解决LCS ...3.实现三个字符串最长公共子序列的动态规划算法 4.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析了算法的性能
求解任意两个字符串的最长公共子序列
自己编写的C++程序,求两个字符串的最长公共字串。例如a="abcrrrerads",b="afdabcssbcrrresswrds",则结果为bcrrre
算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
C++求最长公共子序列!实用 花费了好长时间!!
给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。 一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后...
最长公共子序列,求两个字符串的最长公共子序列。
【问题描述】字符序列的子序列是指从给定字符序列中随意地(不一定要联系)去掉若干个字符...给定两个序列A和B,称序列Z是A和B的公共子序列,是指Z同是A和B的子序列,该问题是求两序列A和B的最长公共子序列(LCS)
采用动态规划法与回溯法实现了lcs算法,并显示各算法运行时间,便于对不同的输入数据测试这两个算法的优劣。
输入两个字符串 求解最长公共子序列并输出子序列及长度
例如,对于字符串 "ABCBDAB" 和 "BDCAB",其最长公共子序列是 "BCBA"。 解决LCS问题的一个常用方法是动态规划。动态规划方法将问题分解为更小的子问题,并存储这些子问题的解以避免重复计算。对于LCS问题,我们可以...
求两个字符串序列的最长公共子序列,利用动态规划求出最优解。