问题:最长公共子序列不要求所求得的字符串在所给字符串中是连续的,如输入两个字符串ABCBDAB和BDCABA,字符串BCBA和BDAB都是他们的公共最长子序列
该问题属于动态规划问题
解答:设序列X=<x0,x1,...,xm>和Y=<y0,y1,...,yn>的一个最长公共子序列为Z=<z0,z1,...,zk>,则:
1)若xm=yn,则必然有zk=xm=yn,则zk-1是xm-1和yn-1的最长公共子序列;
2)若xm≠yn且zk≠xm,则Z是Xm-1和Y的最长公共子序列;
3)若xm≠yn且zk≠yn,则Z是X和Yn-1的最长公共子序列;
也就是说:
当xm=yn时,LCS(Xm,Yn)=LCS(Xm-1,,Yn-1)+1;
当xm≠yn时,LCS(Xm,Yn)=max{LCS(Xm-1,,Yn),LCS(Xm,Yn-1)};
当X,Y为空时,LCS长度为0;
#include<iostream>
#include<cmath>
#define INF 9999999
using namespace std;
int a[][]; //记录已经计算过的子问题
int fun(const char* str1,const char* str2,int i,int j)
{
if(a[i][j]<INF)return a[i][j]; //表示该子问题已经计算过
else if(i==||j==) a[i][j]=;
else if(str1[i-]==str2[j-]) a[i][j]=fun(str1,str2,i-,j-)+;
else a[i][j]=max(fun(str1,str2,i-,j),fun(str1,str2,i,j-));
return a[i][j];
}
int longest(const char* str1,const char* str2)
{
int m=strlen(str1);
int n=strlen(str2);
memset(a,INF,sizeof(a)); //将a的元素设置为INF
return fun(str1,str2,m,n);
}
int main()
{
char *str1=new char[],*str2=new char[];
cout<<"input first string:";
cin>>str1;
cout<<"input second string:";
cin>>str2;
cout<<"the longest length of sunstring is:";
cout<<longest(str1,str2)<<endl;
delete []str1;
delete []str2;
}
结果: