// 最长公共子序列问题.cpp : Defines the entry point for the console application.
//动态规划问题
对于X=x1x2...xm, Y=y1y2...yn的最长公共子序列Z=z1z2...zk
1)、如果xm=yn,那么zk=xm=yn,且Zk-1是Xm-1和Yn-1的一个LCS
2)、如果xm!=yn,那么zk!=xm蕴含Z是Xm-1和Y的一个LCS
3)、如果xm!=yn,那么zk!=yn蕴含Z是X和Yn-1的一个LCS
最长公共子序列的长度
#include "stdafx.h"
#include<iostream>
#define N 1000
using namespace std;
//str1存储字符串1,str2存储字符串2
char str1[N],str2[N];
//lcs存储最长公共子序列
char lcs[N];
//c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度
int c[N][N];
//flag[i][j]标记是那种子问题
//flag[i][j]==0为str1[i]==str2[j]
//flag[i][j]==1为c[i-1][j]>=s[i][j-1]
//flag[i][j]==-1为c[i-1][j]<s[i][j-1]
int flag[N][N];
//
int getLCSlength(const char *s1, const char *s2)
{
int i;
int len1 = strlen(s1);
int len2 = strlen(s2);
for(i=1;i<=len1;i++)
c[i][0] = 0;
for(i=0;i<=len2;i++)
c[0][i] = 0;
int j;
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
{
if(s1[i-1]==s2[j-1])
{
c[i][j] = c[i-1][j-1] +1;
flag[i][j] = 0;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j] = c[i-1][j];
flag[i][j] = 1;
}
else
{
c[i][j] = c[i][j-1];
flag[i][j] = -1;
}
}
return c[len1][len2];
}
char* getLCS(const char *s1, const char *s2,int len,char *lcs)
{
int i = strlen(s1);
int j = strlen(s2);
while(i&&j)
{
if(flag[i][j]==0)
{
lcs[--len] = s1[i-1];
i--;
j--;
}
else if(flag[i][j]==1)
i--;
else
j--;
}
return lcs;
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例的个数:"<<endl;
cin>>cases;
while(cases--)
{
int i;
cout<<"请输入字符串1:"<<endl;
cin>>str1;
cout<<"请输入字符串2:"<<endl;
cin>>str2;
int lcsLen = getLCSlength(str1,str2);
cout<<"最长公共子序列长度:"<<lcsLen<<endl;
char *p = getLCS(str1,str2,lcsLen,lcs);
cout<<"最长公共子序列为:"<<endl;
for(i=0;i<lcsLen;i++)
cout<<lcs[i];
cout<<endl;
}
system("pause");
return 0;
}
请输入案例的个数:
1
请输入字符串1:
abcbdab
请输入字符串2:
bdcaba
最长公共子序列长度:4
最长公共子序列为:
bcba
请按任意键继续. . .
分享到:
相关推荐
最长公共子序列及杭电1394的求解 求解字符串公共子串的问题
最长公共子序列模版
12个ACM动态规划经典题 习题+分析+程序 (转载)
在编程中会要求最长子序列....这就是经典的动态规划里的最大公共子序列!
ACM ICPC程序设计与分析(C++实现)全本,挺厚的一本书,看的时候抓住关键点去看
1.Fibonacci Numbers 2.矩阵连乘问题 3.MAX SUM 4.最长公共子序列 5.Number Triangles 6.编辑距离问题 7.Pebble Merging 8.租用游艇问题 . .
acm动态规划经典题,有助于增加对动态规划的理解与应用
动态规划---做acm的人都知道,很难入门,本资源提供入门窗口
暑假学校ACM集训用的课件,动态规划专题。
acm 动态规划 必做50题目
ACM 编程 算法 之动态规划 课件讲义
经典ACM算法(母函数,动态规划,)很经典
基于C++的ACM模板
本次课程论文,针对ACM比赛中的经典算法,动态规划,进行了详细的讲述,并以ZOJ和POJ上的经典题目为例,讲述了动态规划算法的应用。
acm,背包问题大全,详细讲解,内容齐全,概括到位,c++
3.徐持衡《浅谈几类背包题》 8.徐源盛《对一类动态规划问题的研究》 背包九讲Pack 【专辑】插头DP 【专辑】单调队列+斜率优化的DP ...最长公共子序列和字符串相似度 最大矩阵连乘次数(最小连乘变形)
该课件详细讲述了acm方面关于动态规划法的原理,有背包原型,有最大子段和,有最长连续子序列,最短路径等等。
ACM中的动态规划中的状态压缩问题,有讲解和例题。
基于C++实现的ACM-ACM竞赛常用模板