在兩個字符串中，有些字符會一樣，可以形成的子序列也有可能相等，因此，長度最長的相等子序列便是兩者間的最長公共字序列，其長度可以使用動態(tài)規(guī)劃來求。

以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}為例。

借用《算法導論》中的推導圖：

創(chuàng)建 DP數(shù)組C[][];

圖中的空白格子需要填上相應的數(shù)字（這個數(shù)字就是c[i][j]的定義，記錄的LCS的長度值）。填的規(guī)則依據(jù)遞歸公式，簡單來說：如果橫豎（i,j）對應的兩個元素相等，該格子的值 = c[i-1,j-1] + 1。如果不等，取c[i-1,j] 和 c[i,j-1]的最大值。首先初始化該表：

然后，一行一行地從上往下填：

S1的元素3 與 S2的元素3 相等，所以 c[2,1] = c[1,0] + 1。繼續(xù)填充：

S1的元素3 與 S2的元素5 不等，c[2,2] =max(c[1,2],c[2,1])，圖中c[1,2] 和 c[2,1] 背景色為淺黃色。

繼續(xù)填充：

中間幾行填寫規(guī)則不變，直接跳到最后一行：

至此，該表填完。根據(jù)性質(zhì)，c[8,9] = S1 和 S2 的 LCS的長度，即為5。

得到公式

代碼

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

using namespace std;

const int MAXN = 1005;

int DP[MAXN][MAXN];

int main()

{

string a;

string b;

while(cin >> a >> b)

{

int l1 = a.size();

int l2 = b.size();

memset(DP, 0, sizeof(DP));

for(int i = 1; i <= l1; i++)

for(int j = 1; j <= l2; j++)

if(a[i - 1] == b[j - 1])

DP[i][j] = max(DP[i][j], DP[i - 1][j - 1] + 1);

else

DP[i][j] = max(DP[i][j - 1], DP[i - 1][j]);

printf("%dn", DP[l1][l2]);

}

return 0;

}

當?shù)玫酵暾腄P表之后，我們可以通過倒推來得到相應的子序列

S1和S2的最LCS并不是只有1個，本文并不是著重講輸出兩個序列的所有LCS，只是介紹如何通過上表，輸出其中一個LCS。

我們根據(jù)遞歸公式構建了上表，我們將從最后一個元素c[8][9]倒推出S1和S2的LCS。

c[8][9] = 5，且S1[8] != S2[9]，所以倒推回去，c[8][9]的值來源于c[8][8]的值(因為c[8][8] > c[7][9])。

c[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去，c[8][8]的值來源于 c[7][7]。

以此類推，如果遇到S1[i] != S2[j] ，且c[i-1][j] = c[i][j-1] 這種存在分支的情況，這里請都選擇一個方向（之后遇到這樣的情況，也選擇相同的方向）。

第一種結果為：

這就是倒推回去的路徑，棕色方格為相等元素，即LCS = {3,4,6,7,8}，這是其中一個結果。

如果如果遇到S1[i] != S2[j] ，且c[i-1][j] = c[i][j-1] 這種存在分支的情況，選擇另一個方向，會得到另一個結果。

即LCS ={3,5,7,7,8}。

在倒推時，如果s1[i] == s2[j] 就跳轉到c[i - 1][j - 1],如果s1[i] != s1[j], 就向前找或向上找（只能一個方向）

PS：在代碼中和解說中代碼細節(jié)有所不同，在解說圖中s從下標1開始，在代碼中從下標0開始。

---------------------

作者：someone_and_anyone

總結

以上是生活随笔為你收集整理的c语言最长公共子序列_LCS（最长公共子序列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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