LCS最长公共子序列
问题：最长公共子序列不要求所求得的字符串在所给字符串中是连续的，如输入两个字符串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；
1 #include<iostream> 2 #include<cmath> 3 #define INF 9999999 4 using namespace std; 5 int a[100][100]; //记录已经计算过的子问题 6 int fun(const char* str1,const char* str2,int i,int j) 7 { 8 if(a[i][j]<INF)return a[i][j]; //表示该子问题已经计算过 9 else if(i==0||j==0) a[i][j]=0; 10 else if(str1[i-1]==str2[j-1]) a[i][j]=fun(str1,str2,i-1,j-1)+1; 11 else a[i][j]=max(fun(str1,str2,i-1,j),fun(str1,str2,i,j-1)); 12 return a[i][j]; 13 } 14 int longest(const char* str1,const char* str2) 15 { 16 int m=strlen(str1); 17 int n=strlen(str2); 18 memset(a,INF,sizeof(a)); //将a的元素设置为INF 19 return fun(str1,str2,m,n); 20 } 21 int main() 22 { 23 char *str1=new char[100],*str2=new char[100]; 24 cout<<"input first string:"; 25 cin>>str1; 26 cout<<"input second string:"; 27 cin>>str2; 28 cout<<"the longest length of sunstring is:"; 29 cout<<longest(str1,str2)<<endl; 30 delete []str1; 31 delete []str2; 32 }
结果：