一、什么是LCS

LCS（Longest Common Subsequence）是最長公共子序列。顧名思義，就是兩個或多個已知序列的最長的公共的子序列。那么什么是子序列呢？

字符子序列：簡單來說就是去掉一個字符串中的某些字符（可以不連續）后剩下的新字符串（不可調整字符順序）。例如字符串abcdefg,那么新字符串abcd,aceg就是原字符串的字符子序列，但是abcd,geca就不是，這是因為后兩個字符串的順序不符合原字符串。

二、提取LCS的方法原理

1. 求LCS的長度

我們用兩個字符數組
a[m],b[n],
表示要提取出LCS的兩個原字符串，

二維數組
lenlcs[i][j]
表示字符數組a[i],b[j]（表示原字符數組取前i,j個元素的子字符數組）的LCS的長度并初始化為0。

注意: 當i和j取定一個值時，lenlcs[i][j] 就等于一個數，這個數是原字符數組（字符串）a[m],b[n] 分別取前i和j個字符所得兩個新字符串的LCS的長度。

首先考慮兩個原字符數組的最后一項，假設現在的a[i]和b[j]分別表示原字符數組的最后一個元素，那么就分為了以下兩種情況：

① a[i] == b[j]

那么LCS的最后一個字符就是a[i]或b[j]。
這一點可以用反證法證明：如果LCS最后一個字符不是a[i]或b[j]，那么就可以在所謂的LCS末尾加上a[i]或b[j]而使得LCS更長（長度+1）。此時LCS的長度就等于原字符數組分別去掉最后一個字符后的兩個新字符數組的LCS的長度加上1，即：

lenlcs[i][j] = lenlcs[i-1][j-1] + 1

② a[i] != b[j]

那么就要考慮去掉原字符數組最后一個元素后的兩個字符數組（一個字符數組去掉最后一個元素，一個不去掉）的LCS，這是因為既然最長的原字符數組的最后一個元素不參與構成LCS，那就要考慮短一點的原字符數組，那就將兩個原字符數組中的一個去掉一個字符構成新的兩個原字符數組，再比較這兩個新原字符數組的最后一個元素。

顯然，我們要取使得新的LCS更長的兩個原字符數組，即：

lenlcs[i][j] = max { lenlcs[i-1][j] , lenlcs[i][j-1] }

小結

根據以上兩種情況

lenlcs[i][j] =
lenlcs[i-1][j-1] + 1 , 當 a[i] == b[j]；
max { lenlcs[i-1][j] , lenlcs[i][j-1] } , 當 a[i] != b[j] 。

max部分可以再分開為兩種小情況，總的來說不考慮結束條件是三種小情況。

顯然，當 i=0 或 j=0 時 lenlcs[i][j]=0 （當某一個原字符串長度為0時就沒有子字符序列，當然對應的LCS長度為0）。
雖然我們推導時是從 lenlcs[i][j] 開始由后向前，但我們計算時就可以根據這個式子由前向后（從 i , j 等于0時開始）求出每一個 i , j 對應的 lenlcs[i][j]，最終 lenlcs[m][n] 就表示最初的字符數組 a[m],b[n] 的LCS的長度。

核心代碼

void clenlcs()//求LCS的長度 {int i,j;for(i=1;i<=m;++i)//從1開始，防止出現lenlcs[-1][-1] {for(j=1;j<=n;++j)//對應三種小情況 {if(a[i-1]==b[j-1])//因為i,j從1開始，所以a[0]就是a[i-1]lenlcs[i][j]=lenlcs[i-1][j-1]+1;//注意a[0],b[0]對應lenlcs[1][1],而不是lenlcs[0][0]else if(lenlcs[i-1][j]>lenlcs[i][j-1])//當然也可以寫成>=lenlcs[i][j]=lenlcs[i-1][j];elselenlcs[i][j]=lenlcs[i][j-1];}}//可以在這個位置輸出lenlcs[m][n],也可以單獨寫一個output函數連同之后求出的LCS一起輸出。}

2. 求LCS

我們用字符數組
lcs[x]
來存放LCS

同樣的，需要考慮以下兩種情況：

① a[i] == b[j]

那么
lcs[k]= a[i]
或
lcs[k]= b[j]

② a[i] != b[j]

那么需要考慮 lenlcs[i-1][j] 和 lenlcs[i][j-1] 的大小，取大的，并繼續比較 a[i-1] 和 b[j] ，或 a[i] 和 b[j-1] 。當然比較過程也可以再分為兩種小情況。

最后結束循環的條件是 i=0 或 j=0 。

由此可以得到倒序排列的LCS，通過函數再倒序一次就可以得到真正的LCS。

核心代碼

void clcs()//求LCS{int i,j,k=0;i=m;//strlen(a)j=n;//strlen(b)while(i!=0 && j!=0)//對應三種小情況 {if(a[i-1]==b[j-1])//用i-1,j-1是因為i,j最初等于m,n，沒有a[m],b[n]這兩個字符{lcs[k]=a[i-1];//在上面，k最初等于0--i;--j;++k;}else if(lenlcs[i-1][j]>lenlcs[i][j-1])//如果去掉a最后元素所得LCS長度大于去掉b最后元素，那么去掉a最后元素 --i;else if(lenlcs[i-1][j]<=lenlcs[i][j-1])--j;}turn();//調整LCS字符順序，這個函數也是自己寫的，可以在下面的完整代碼中找到。}

三、完整代碼

#include<iostream> #include<cstring> using namespace std;class test { private:char a[101],b[101],lcs[101];//假設原數組元素字符數量不超過100int m,n;//m=strlen(a),n=strlen(b)int lenlcs[101][101];//LCS的長度 public:test()//初始化，將lenlcs[][]和lcs[]中的所有元素初始化為0.{memset(lenlcs,0,sizeof(lenlcs));memset(lcs,0,sizeof(lcs));}void input(){cout<<"input string a and string b: ";cin>>a;cin>>b;m=strlen(a);n=strlen(b);}void turn()//調整LCS字符順序 {char llcs[101];int i,len=strlen(lcs);for(i=0;i<len;++i){llcs[i]=lcs[len-i-1];//將倒序后的字符串放入llcs[]}for(i=0;i<len;++i){lcs[i]=llcs[i];//將lcs等于llcs.}}void clenlcs()//求LCS的長度 {int i,j;for(i=1;i<=m;++i)//從1開始，防止出現lenlcs[-1][-1] {for(j=1;j<=n;++j)//對應三種情況 {if(a[i-1]==b[j-1])//因為i,j從1開始，所以a[0]就是a[i-1]lenlcs[i][j]=lenlcs[i-1][j-1]+1;//注意a[0],b[0]對應lenlcs[1][1],而不是lenlcs[0][0]else if(lenlcs[i-1][j]>lenlcs[i][j-1])//當然也可以寫成>=lenlcs[i][j]=lenlcs[i-1][j];elselenlcs[i][j]=lenlcs[i][j-1];}}//可以在這個位置輸出lenlcs[m][n],也可以單獨寫一個output函數連同之后求出的LCS一起輸出。}void clcs()//求LCS{int i,j,k=0;i=m;//strlen(a)j=n;//strlen(b)while(i!=0 && j!=0)//對應三種小情況 {if(a[i-1]==b[j-1])//用i-1,j-1是因為i,j最初等于m,n，沒有a[m],b[n]這兩個字符{lcs[k]=a[i-1];//在上面，k最初等于0--i;--j;++k;}else if(lenlcs[i-1][j]>lenlcs[i][j-1])//如果去掉a最后元素所得LCS長度大于去掉b最后元素，那么去掉a最后元素 --i;else if(lenlcs[i-1][j]<=lenlcs[i][j-1])--j;}turn();//調整LCS字符順序，這個函數也是自己寫的，可以在下面的完整代碼中找到。} void output(){clenlcs();clcs();cout<<"The Length of LCS: "<<lenlcs[m][n]<<endl;//注意不是lenlcs[m-1][n-1]cout<<"LCS: "<<lcs<<endl;} };int main() {test t;//abcicba abdkscabt.input();t.output();return 0; }

參考文章：
https://blog.csdn.net/lxt_lucia/article/details/81209962
https://blog.csdn.net/lz161530245/article/details/76943991

總結

以上是生活随笔為你收集整理的提取LCS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。