程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 【51NOD】1006 最長公共子序列Lcs(靜態規劃)

【51NOD】1006 最長公共子序列Lcs(靜態規劃)

編輯:關於C++

【51NOD】1006 最長公共子序列Lcs(靜態規劃)。本站提示廣大學習愛好者:(【51NOD】1006 最長公共子序列Lcs(靜態規劃))文章只能為提供參考,不一定能成為您想要的結果。以下是【51NOD】1006 最長公共子序列Lcs(靜態規劃)正文


給出兩個字符串A B,求A與B的最長公共子序列(子序列不要求是延續的)。

比方兩個串為:   abcicba abdkscab   ab是兩個串的子序列,abc也是,abca也是,其中abca是這兩個字符串最長的子序列。 Input
第1行:字符串A
第2行:字符串B
(A,B的長度 <= 1000)
Output
輸入最長的子序列,假如有多個,隨意輸入1個。
Input示例
abcicba
abdkscab
Output示例
abca

問題定義
• 子序列
– X=(A, B, C, B, D, B)
– Z=(B, C, D, B)是X的子序例
– W=(B, D, A)不是X的子序例
• 公共子序列
–Z是序列X與Y的公共子序列假如Z是X的
子序也是Y的子序列。
最長公共子序列(LCS)問題
輸出:X = (x1,x2,...,xn),Y =
(y1,y2,...ym)
輸入:Z = X與Y的最長公共子序

最長公共子序列構造剖析
• 第i前綴
– 設X=(x1, x2, ..., xn)是一個序列,X的第i前
綴Xi
是一個序列,定義為Xi=(x1, ..., xi )
例. X=(A, B, D, C, A), X1=(A), X2=(A, B), X3=(A,
B, D)
優化子構造
定理1(優化子構造)設X=(x1, ..., xm)、
Y=(y1, ..., yn) 是兩個序列,Z=(z1, ..., zk)是X與Y的
LCS,我們有:
⑴ 假如xm=yn, 則zk=xm=yn, Zk-1
是Xm-1
和Yn-1

LCS,即,LCSXY = LCSXm-1Yn-1
+ <xm=yn>.
⑵ 假如xm.yn
,且zk.xm
,則Z是Xm-1
和Y的
LCS,即 LCSXY= LCSXm-1Y
⑶ 假如xm.yn,且zk.yn,則Z是X與Yn-1
的LCS,
即 LCSXY= LCSXYn-1
證明:
⑴. X=<x1, …, xm-1, xm>, Y=<y1, …, yn-1, xm>,則
LCSXY = LCSXm-1Yn-1
+ <xm=yn>.
設zkxm
,則可加xm=yn
到Z,失掉一個長為k+1的
X與Y的公共序列,與Z是X和Y的LCS矛盾。於是
zk=xm=yn

如今證明Zk-1
是Xm-1
與Yn-1
的LCS。顯然Zk-1
是Xm-
1
與Yn-1
的公共序列。我們需求證明Zk-1
是LCS。
設不然,則存在Xm-1
與Yn-1
的公共子序列W,W
的長大於k-1。添加xm=yn
到W,我們失掉一個長
大於k的X與Y的公共序列,與Z是LCS矛盾。於
是,Zk-1
是Xm-1
與Yn-1
的LCS.
⑵ X=<x1, …, xm-1, xm>, Y=<y1, …, yn-1, yn>,
xmyn
,zkxm
,則 LCSXY= LCSXm-1Y
由於zkxm
,Z是Xm-1
與Y的公共子序列。我
們來證Z是Xm-1
與Y的LCS。設Xm-1
與Y有一
個公共子序列W,W的長大於k, 則W也是X
與Y 的公共子序列,與Z是LCS矛盾。
⑶ 同⑵可證。
X和Y的LCS的優化解構造為
LCSXY=LCSXm-1Yn-1
+ <xm=yn> if xm=yn
LCSXY=LCSXm-1Y if xm≠yn, zk≠xm
LCSXY=LCSXYn-1 if xm≠yn, zk≠yn

樹立LCS長度的遞歸方程
• C[i, j] = Xi與Yj 的LCS的長度
• LCS長度的遞歸方程
C[i, j] = 0 if i=0 或 j=0
C[i, j] = C[i-1, j-1] + 1 if i, j>0 且 xi = yj
C[i, j] = Max(C[i, j-1], C[i-1, j]) if i, j>0 且 xi ≠ yj


自底向上計算LCS的長度

計算LCS長度的算法
– 數據構造
C[0:m,0:n]: C[i,j]是Xi
與Yj
的LCS的長度
B[1:m,1:n]: B[i,j] 是指針, 指向計算
C[i,j]時所選擇的子問題的優化解所對
應的C表的表項

LCS-length(X, Y)
m←length(X);n←length(Y);
For i←1 To m Do C[i,0]←0;
For j←1 To n Do C[0,j]←0;
For i←1 To m Do
For j←1 To n Do
If xi = yj
Then C[i,j]←C[i-1,j-1]+1;B[i,j]←“↖”;
Else If C[i-1,j]≥C[i,j-1]
Then C[i,j]≥C[i-1,j]; B[i,j]←“↑”;
Else C[i,j]≥C[i,j-1]; B[i,j]←“←”;
Return C and B.
結構優化解
• 根本思想
– 從B[m, n]開端按指針搜索
– 若B[i, j]=“↖”,則xi=yj
是LCS的一個元

– 如此找到的“LCS”是X與Y的LCS
Print-LCS(B, X, i, j)
IF i=0 or j=0 THEN Return;
IF B[i, j]=“↖”
THEN Print-LCS(B, X, i-1, j-1);
Print xi;
ELSE If B[i, j]=“↑”
THEN Print-LCS(B, X, i-1, j);
ELSE Print-LCS(B, X, i, j-1).

Print-LCS(B, X, length(X), length(Y))
可打印出X與Y的LCS。
 1      /*功用:計算最優值
 2       *參數:
 3       *        x:字符串x  X:字符串x最大長度
 4       *        y:字符串y   Y:字符串y最大長度
 5       *        b:標志數組
 6       *        xlen:字符串x的長度
 7       *        ylen:字符串y的長度
 8       *前往值:最長公共子序列的長度
 9       *
10       */
11      int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen)
12      {
13          int i = 0;
14          int j = 0;
15 
16          int c[X+1][Y+1];
17          for (i = 0; i<=xlen; i++)
18          {
19              c[i][0]=0;
20          }
21          for (i = 0; i <= ylen; i++ )
22          {
23              c[0][i]=0;
24          }
25          for (i = 1; i <= xlen; i++)
26          {
27             
28              for (j = 1; j <= ylen; j++)
29              {
30                  if (x[i - 1] == y[j - 1])
31                  {
32                      c[i][j] = c[i-1][j-1]+1;
33                      b[i][j] = 1;
34                  }
35                  else
36                      if (c[i-1][j] > c[i][j-1])
37                      {
38                          c[i][j] = c[i-1][j];
39                          b[i][j] = 2;
40                      }
41                      else
42                          if(c[i-1][j] <= c[i][j-1])
43                          {
44                              c[i][j] = c[i][j-1];
45                              b[i][j] = 3;
46                          }
47                          
48              }
49          }
50          
51          cout << "計算最優值效果圖如下所示:" << endl;
52          for(i = 1; i <= xlen; i++)
53          {
54              for(j = 1; j < ylen; j++)
55              {
56                  cout << c[i][j] << " ";
57              }
58              cout << endl;
59          }
60          
61          return c[xlen][ylen];
62      }

完好代碼

    //只能打印一個最長公共子序列
    #include <iostream>
    using namespace std;
     
     const int X = 1000, Y = 1000;        //串的最大長度
     char result[X+1];                    //用於保管後果
     int count=0;                        //用於保管公共最長公共子串的個數
 	 int c[X+1][Y+1];
 	 int b[X + 1][Y + 1];
     /*功用:計算最優值
      *參數:
      *        x:字符串x
      *        y:字符串y
      *        b:標志數組
      *        xlen:字符串x的長度
      *        ylen:字符串y的長度
      *前往值:最長公共子序列的長度
      *
      */
     int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen)
     {
         int i = 0;
         int j = 0;

         //int c[X+1][Y+1];
         for (i = 0; i<=xlen; i++)
         {
             c[i][0]=0;
         }
         for (i = 0; i <= ylen; i++ )
         {
             c[0][i]=0;
         }
         for (i = 1; i <= xlen; i++)
         {
            
             for (j = 1; j <= ylen; j++)
             {
                 if (x[i - 1] == y[j - 1])
                 {
                     c[i][j] = c[i-1][j-1]+1;
                     b[i][j] = 1;
                 }
                 else
                     if (c[i-1][j] > c[i][j-1])
                     {
                         c[i][j] = c[i-1][j];
                         b[i][j] = 2;
                     }
                     else
                         if(c[i-1][j] <= c[i][j-1])
                         {
                             c[i][j] = c[i][j-1];
                             b[i][j] = 3;
                         }
                         
             }
         }
         /*
         cout << "計算最優值效果圖如下所示:" << endl;
         for(i = 1; i <= xlen; i++)
         {
             for(j = 1; j < ylen; j++)
             {
                 cout << c[i][j] << " ";
             }
             cout << endl;
         }
         */
         return c[xlen][ylen];
     }
     
    void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_Len)
     {
         if (i ==0 || j==0)
         {
             return;
         }
         if(b[i][j]== 1)
         {
             current_Len--;
             result[current_Len]=x[i- 1];
             Display_Lcs(i-1, j-1, x, b, current_Len);
         }
         else
         {
             if(b[i][j] == 2)
             {
                 Display_Lcs(i-1, j, x, b, current_Len);
             }
             else
             {
                 if(b[i][j]==3)
                 {
                     Display_Lcs(i, j-1, x, b, current_Len);
                 }
                 else
                 {
                     Display_Lcs(i-1,j,x,b, current_Len);
                 }
             }
         }
     }
     
     int main(int argc, char* argv[])
     {
         string x;
         string y;
         cin>>x>>y;
         int xlen = x.length();
         int ylen = y.length();

         //int b[X + 1][Y + 1];

         int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );
         //cout << lcs_max_len << endl;

         Display_Lcs( xlen, ylen, x, b, lcs_max_len );
         
         //打印後果如下所示
        for(int i = 0; i < lcs_max_len; i++)
        {
            cout << result[i];
        }
        cout << endl;
         return 0;
     }

 算法復雜性:

• 時間復雜性
– 計算代價的時間
• (i, j)兩層循環,i循環m步, j循環n步
• O(mn)
– 結構最優解的時間: O(m+n)
– 總時間復雜性為:O(mn)
• 空降復雜性
– 運用數組C和B
– 需求空間O(mn)

 

 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved