LCS最長公共子序列，LCS公共子序列

LCS最長公共子序列，LCS公共子序列

問題：最長公共子序列不要求所求得的字符串在所給字符串中是連續的，如輸入兩個字符串ABCBDAB和BDCABA,字符串BCBA和BDAB都是他們的公共最長子序列

該問題屬於動態規劃問題

解答：設序列X=<x₀,x₁,...,x_m>和Y=<y₀,y₁,...,y_n>的一個最長公共子序列為Z=<z₀,z₁,...,z_k>,則：

1）若x_m=y_n,則必然有z_k=x_m=y_n,則z_k-1是x_m-1和y_n-1的最長公共子序列；

2)若x_m≠y_n且z_k≠x_m,則Z是X_m-1和Y的最長公共子序列；

3)若x_m≠y_n且z_k≠y_n,則Z是X和Y_n-1的最長公共子序列；

也就是說：

當x_m=y_n時，LCS(X_m,Y_n)=LCS(X_m-1,,Y_n-1)+1;

當x_m≠y_n時，LCS(X_m,Y_n)=max{LCS(X_m-1,,Y_n）,LCS(X_m,Y_n-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 }

結果：