长公共子序列问题(00002).docx

最长公共子序列问题:(递归与动态规划实现)

注:
(1)递归方法求最长公共子序列的长度
1)设有字符串a[0...n],b[0...m],下面就是递推公式。
             当数组a和b对应位置字符相同时,则直接求解下一个位置;当不同时取两种情况中的较大数值。
LCS(I,j)=1+LCS(i-1,j-1);( a[i]=b[j])
或者=MAX(LCS(I,j-1),LCS(i-1,j);(a[i]不等于b[j])
#include<iostream>
#include<cstdio>
#include<string>
#include<>
using namespace std;
string lcsstr;
#define N 30
int xlen,ylen;
int c[N][N];
int maxlen;
int LCS(char*x,char*y,string d,int i,int j,int len)
{
if(i<0||j<0)
{
if(len>maxlen)
{ maxlen=len;
lcsstr=d;
}
return 0;
}
xlen=strlen(x);
ylen=strlen(y);
if(x[i]==y[j])
{
d=x[i]+d;
return c[i][j]=LCS(x,y,d,i-1,j-1,len+1)+1;
}
else return LCS(x,y,d,i-1,j,len)>LCS(x,y,d,i,j-1,len)?LCS(x,y,d,i-1,j,len):LCS(x,y,d,i,j-1,len);
}
int main()
{
char s1[N];
char s2[N];
int i,j,num;
char*s=new char[N];
string d;
double t,tt;
cout<<"输º?入¨?第̨²一°?个?字Á?串ä?:"<<endl;
cin>>s1;
i=strlen(s1);
cout<<"输º?入¨?第̨²二t个?字Á?串ä?:êo"<<endl;
cin>>s2;
j=strlen(s2);
t=clock();
num= LCS(s1,s2,d,i-1,j-1,0);
tt=clock()-t;

cout<<num<<","<<lcsstr<<endl;
cout<<"运?行D时º¡À间?:êo"<<tt<<endl;
system("pause");
}
以下是用递归实现输出最长公共子序列的运行截图:
(2)动态规划:
(2)动态规划求最长公共子序列的长度
动态规划采用二维数组来标识中间计算结果,避免重复的计算来提高效率。
1)最长公共子序列的长度的动态规划方程
设有字符串a[0...n],b[0...m],下面就是递推公式。字符串a对应的是二维数组num的行,字符串b对应的是二维数组num的列。
#include<iostream>
#include<>
#include<strin