最長(zhǎng)公共子序列問題LCS

??問題描寫敘述：

一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說。若給定序列X=?{ x1, x2,…, xm}，則還有一序列Z= {z1, z2,…, zk}是X的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列 {i1, i2,…, ik}，使得對(duì)于全部j=1,2,…,k有 Xij=Zj。比如，序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列。對(duì)應(yīng)的遞增下標(biāo)序列為{2,3,5,7}。給定兩個(gè)序列X和Y，當(dāng)還有一序列Z既是X的子序列又是Y的子序列時(shí)。稱Z是序列X和Y的公共子序列。比如，若X=?{ A, B, C, B, D, A, B}和Y=?{B, D, C, A, B, A}，則序列{B,C,A}是X和Y的一個(gè)公共子序列，序列{B,C,B,A}也是X和Y的一個(gè)公共子序列。并且，后者是X和Y的一個(gè)最長(zhǎng)公共子序列。由于X和Y沒有長(zhǎng)度大于4的公共子序列。給定兩個(gè)序列X=?{x1, x2, …, xm}和Y=?{y1, y2, … , yn}，要求找出X和Y的一個(gè)最長(zhǎng)公共子序列。

? ? ?問題解析：

設(shè)X= { A, B, C, B, D, A, B},Y= {B, D, C, A, B, A}。求X，Y的最長(zhǎng)公共子序列最easy想到的方法是窮舉法。

對(duì)X的多有子序列，檢查它是否也是Y的子序列。從而確定它是否為X和Y的公共子序列。由集合的性質(zhì)知，元素為m的集合共同擁有2^m個(gè)不同子序列，因此，窮舉法須要指數(shù)級(jí)別的運(yùn)算時(shí)間。進(jìn)一步分解問題特性。最長(zhǎng)公共子序列問題實(shí)際上具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

????? 設(shè)序列X={x1,x2,……xm}和Y={y1,y2,……yn}的最長(zhǎng)公共子序列為Z={z1,z2,……zk}。則有：

????? (1)若xm=yn,則zk=xm=yn,且zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。

????? (2)若xm!=yn且zk!=xm，則Z是Xm-1和Y的最長(zhǎng)公共子序列。

????? (3)若xm!=yn且zk!=yn。則Z是X和Yn-1的最長(zhǎng)公共子序列。

????? 當(dāng)中，Xm-1={x1,x2……xm-1}。Yn-1={y1,y2……yn-1},Zk-1={z1,z2……zk-1}。

• 若xm=yn（最后一個(gè)字符同樣）。則不難用反證法證明：該字符必是X與Y的任一最長(zhǎng)公共子序列Z（設(shè)長(zhǎng)度為k）的最后一個(gè)字符，即有zk = xm = yn 且顯然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前綴Zk-1是Xm-1與Yn-1的最長(zhǎng)公共子序列。此時(shí)。問題化歸成求Xm-1與Yn-1的LCS（LCS(X , Y)的長(zhǎng)度等于LCS(Xm-1 , Yn-1)的長(zhǎng)度加1）。

• 若xm≠yn。則亦不難用反證法證明：要么Z∈LCS(Xm-1, Y)。要么Z∈LCS(X , Yn-1)。

  因?yàn)閦k≠xm與zk≠yn當(dāng)中至少有一個(gè)必成立，若zk≠xm則有Z∈LCS(Xm-1 , Y)，類似的，若zk≠yn 則有Z∈LCS(X , Yn-1)。此時(shí)，問題化歸成求Xm-1與Y的LCS及X與Yn-1的LCS。

  LCS(X , Y)的長(zhǎng)度為：max{LCS(Xm-1 , Y)的長(zhǎng)度, LCS(X , Yn-1)的長(zhǎng)度}。

? ? ?遞推關(guān)系：

用c[i][j]記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。當(dāng)中，Xi={x1,x2……xi}。Yj={y1,y2……yj}。當(dāng)i=0或j=0時(shí)，空序列是xi和yj的最長(zhǎng)公共子序列。此時(shí)。c[i][j]=0；當(dāng)i,j>0，xi=yj時(shí)，c[i][j]=c[i-1][j-1]+1；當(dāng)i,j>0，xi!=yj時(shí)。

c[i][j]=max{c[i][j-1],c[i-1][j]}，由此建立遞推關(guān)系例如以下：

??????????構(gòu)造最優(yōu)解：

由以上分析可知，要找出X={x1,x2,……xm}和Y={y1,y2,……yn}的最長(zhǎng)公共子序列,能夠按一下方式遞歸進(jìn)行：當(dāng)xm=yn時(shí)，找出xm-1和yn-1的最長(zhǎng)公共子序列。然后在尾部加上xm(=yn)就可以得X和Y的最長(zhǎng)公共子序列。當(dāng)Xm!=Yn時(shí)，必須解兩個(gè)子問題，即找出Xm-1和Y的一個(gè)最長(zhǎng)公共子序列及X和Yn-1的一個(gè)最長(zhǎng)公共子序列。

這兩個(gè)公共子序列中較長(zhǎng)者為X和Y的最長(zhǎng)公共子序列。設(shè)數(shù)組record[i][j]記錄c[i][j]的值由哪一個(gè)子問題的解得到的。從record[m][n]開始。依其值在數(shù)組b中搜索，當(dāng)record[i][j]=1時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列是由Xi-1和Yj-1的最長(zhǎng)公共子序列在尾部加上xi所得到的子序列。當(dāng)record[i][j]=2時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列與Xi-1和Yj-1的最長(zhǎng)公共子序列同樣。

當(dāng)record[i][j]=3時(shí)。表示Xi和Yj的最長(zhǎng)公共子序列與Xi和Yj-1的最長(zhǎng)公共子序列同樣。

代碼： #include<iostream> #include<cstdio> #include<string> #include<algorithm> #define MAX 1000using namespace std;int dp[MAX][MAX]; int record[MAX][MAX];int LCSLength(string strA,string strB) {int i,j;int lenA=strA.length();int lenB=strB.length();for(i=0;i<lenA;i++)dp[i][0]=0;for(j=0;j<lenB;j++)dp[0][j]=0;for(i=0;i<lenA;i++){for(j=0;j<lenB;j++){if(i==0||j==0){if(strA[i]==strB[j]){dp[i][j]=1;record[i][j]=1;}else{if(i>0){dp[i][j]=dp[i-1][j];record[i][j]=3;}if(j>0){dp[i][j]=dp[i][j-1];record[i][j]=2;}}}else if(strA[i]==strB[j]){dp[i][j]=dp[i-1][j-1]+1;record[i][j]=1;}else if(dp[i-1][j]>=dp[i][j-1]){dp[i][j]=dp[i-1][j];record[i][j]=3;}else{dp[i][j]=dp[i][j-1];record[i][j]=2;}}}return dp[lenA-1][lenB-1]; }void LCS(int i,int j,string strA) {if(i<0||j<0)return ;if(record[i][j]==1){LCS(i-1,j-1,strA);cout<<strA[i];}else if(record[i][j]==2)LCS(i,j-1,strA);elseLCS(i-1,j,strA); }int main(int argc,char *argv[]) {string strA,strB;cin>>strA>>strB;cout<<"LCSLength: "<<LCSLength(strA,strB)<<endl;cout<<"LCS: ";LCS(strA.length()-1,strB.length()-1,strA);cout<<endl;cout<<"Record:\n";for(int i=0;i<strA.length();i++){for(int j=0;j<strB.length();j++)printf("%3d",record[i][j]);printf("\n");}return 0; } 在這里處理邊界條件(i=0||j=0)分類比較麻煩。事實(shí)上還能夠把它們合并為一條語句； 代碼： <span style="font-size:18px;">#inc</span><span style="font-size: 18px;">lude<cstdio> #include<iostream> #include<string> #include<algorithm> #define MAX 1000using namespace std;int dp[MAX][MAX]; int record[MAX][MAX];int LCSLength(string strA,string strB) {int i,j;int lenA=strA.length();int lenB=strB.length();for(i=0;i<=lenA;i++)dp[i][0]=0;for(j=0;j<=lenB;j++)dp[0][j]=0;for(i=1;i<=lenA;i++){for(j=1;j<=lenB;j++){if(strA[i-1]==strB[j-1])//注意下標(biāo)從0開始，所以這里有些許不一樣{ //dp[i][j]存儲(chǔ)的是Xi-1與Yj-1的最長(zhǎng)LCSdp[i][j]=dp[i-1][j-1]+1;record[i][j]=1;}else if(dp[i-1][j]>=dp[i][j-1]){dp[i][j]=dp[i-1][j];record[i][j]=3;}else{dp[i][j]=dp[i][j-1];record[i][j]=2;}}}return dp[lenA][lenB]; }void LCS(int i,int j,string strA) {if(i==0||j==0)return ;if(record[i][j]==1){LCS(i-1,j-1,strA);cout<<strA[i-1];}else if(record[i][j]==2)LCS(i,j-1,strA);elseLCS(i-1,j,strA); }int main(int argc,char *argv[]) {string strA,strB;cin>>strA>>strB;cout<<"LCSLength: "<<LCSLength(strA,strB)<<endl;cout<<"LCS: ";LCS(strA.length(),strB.length(),strA);cout<<endl;cout<<"Record:\n";for(int i=0;i<=strA.length();i++){for(int j=0;j<=strB.length();j++)printf("%3d",record[i][j]);printf("\n");}return 0; } </span>

LCSLength函數(shù)在計(jì)算最優(yōu)值時(shí)，分別迭代X。Y構(gòu)造數(shù)組b,c。設(shè)數(shù)組每一個(gè)元素單元計(jì)算耗費(fèi)時(shí)間O(1)，則易得算法LCSLength的時(shí)間復(fù)雜度為O(mn)。在算法LCS中，根據(jù)數(shù)組b的值回溯構(gòu)造最優(yōu)解，每一次遞歸調(diào)用使i，或j減小1。從而算法的計(jì)算時(shí)間為O(m+n)。

LCS的回溯構(gòu)造最優(yōu)解步驟例如以下圖所看到的:

轉(zhuǎn)載于:https://www.cnblogs.com/jhcelue/p/6971534.html

總結(jié)

以上是生活随笔為你收集整理的最长公共子序列问题LCS的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。