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

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

 1 /*
 2 ========最長公共子序列========
 3 所用算法 動態規劃
 4 作者 程松
 5 時間 2015/12/11 16:43
 6 所用語言 c++
 7 */
 8 #include<iostream>
 9 #include<cstring>
10 #include<string>
11 using namespace std;
12 const int MAX_LENGTH = 1000;//定義字符串最大長度
13 int c[MAX_LENGTH][MAX_LENGTH];//長度為i的字符串x與長度為j的字符串的最長公共子序列長度
14 int b[MAX_LENGTH][MAX_LENGTH];//做標記
15 string x,y;
16 int x_length,y_length;
17 void init(){
18     cin>>x;
19     cin>>y;
20     x_length = x.size();
21     y_length = y.size(); 
22     c[0][0]=-1;//以下循環i,j從1開始需單獨讓c[0][0]為-1，最初因此原因導致錯誤，勿忘勿忘
23     for(int i=1;i<=x_length;++i){
24         for(int j=1;j<=y_length;++j){
25             c[i][j] = -1;//未計算過設為-1,用作備忘錄
26             b[i][j] = 0;
27         }
28     }
29 }
30 int LCSLength(int i,int j,string x,string y){
31     int maxlength;
32     //記錄此時的長度，做備忘錄
33     if(c[i][j]!=-1){
34         maxlength = c[i][j];
35     }
36     //以下通過最優子結構求解
37     else if(i==0&&j==0){//邊界條件，
38         maxlength = 0;
39     }
40     //以下為狀態轉移方程的實現
41     else if(x[i-1]==y[j-1]){
42         maxlength = LCSLength(i-1,j-1,x,y)+1;
43         b[i][j] = 1;
44     }else if(LCSLength(i-1,j,x,y)>=LCSLength(i,j-1,x,y)){
45         maxlength = LCSLength(i-1,j,x,y);
46         b[i][j] = 2;
47     }else{
48         maxlength = LCSLength(i,j-1,x,y);
49         b[i][j] = 3;
50     }
51     c[i][j] = maxlength;
52     return maxlength;
53 }
54 //LCS()用來求解出最長的序列並將其輸出
55 void LCS(int i,int j,string x){
56     if(i==0||j==0)
57         return;
58     else if(b[i][j]==1){
59         LCS(i-1,j-1,x);
60         cout<<x[i-1];
61     }else if(b[i][j]==2){
62         LCS(i-1,j,x);
63     }else{
64         LCS(i,j-1,x);
65     }
66 }
67 int main(){
68     init();
69     cout<<LCSLength(x_length,y_length,x,y)<<endl;
70     LCS(x_length,y_length,x);
71     return 0;
72 }