# 最長公共子序列 > 原文： [https://www.programiz.com/dsa/longest-common-subsequence](https://www.programiz.com/dsa/longest-common-subsequence) #### 在本教程中，您將學習如何找到最長的公共子序列。 此外，您還將找到 C，C++ ，Java 和 Python 中最長的公共子序列的工作示例。 最長公共子序列（LCS）定義為所有給定序列共有的最長子序列，條件是該子序列的元素不需要占據原始序列內的連續位置。 如果`S1`和`S2`是兩個給定的序列，`Z`是`S1`和`S2`的子序列，則`Z`是`S1`和`S2`的共同子序列。 此外，`Z`必須是`S1`和`S2`的索引的**嚴格增加的序列**。 在嚴格增加的序列中，從原始序列中選擇的元素的索引必須在`Z`中按升序排列。 如果 ``` S1 = {B, C, D, A, A, C, D} ``` 然后，`{A, D, B}`不能是`S1`的子序列，因為元素的順序不相同（即，不是嚴格遞增的序列）。 * * * 讓我們通過一個例子來了解 LCS。 If ``` S1 = {B, C, D, A, A, C, D} S2 = {A, C, D, B, A, C} ``` 然后，常見的子序列是`{B, C}, {C, D, A, C}, {D, A, C}, {A, A, C}, {A, C}, {C, D}, ...` 在這些子序列中，`{C, D, A, C}`是最長的公共子序列。 我們將使用動態規劃來找到這個最長的公共子序列。 在繼續進行之前，如果您還不了解動態規劃，請進行[動態規劃](/dsa/dynamic-programming)。 * * * ## 使用動態規劃查找 LCS 讓我們采取兩個順序：  第一個序列  第二個序列 按照以下步驟查找最長的公共子序列。 1. 創建一個大小為`n+1*m+1`的表，其中`n`和`m`分別為`X`和`Y`的長度。 第一行和第一列用零填充。  初始化表格 2. 使用以下邏輯填充表的每個單元格。 3. 如果對應于當前行和當前列的字符匹配，則通過在對角線元素上添加一個來填充當前單元格。 用箭頭指向對角線單元。 4. 否則，取前一列和前一行元素中的最大值以填充當前單元格。 用箭頭指向具有最大值的單元格。 如果它們相等，則指向它們中的任何一個。  填寫值 5. **重復步驟 2** ，直到填滿表格。  填寫所有值 6. 最后一行和最后一列中的值是最長公共子序列的長度。  右下角是 LCS 的長度 7. 為了找到最長的公共子序列，請從最后一個元素開始并遵循箭頭的方向。 與`()`符號相對應的元素形成最長的公共子序列。  根據箭頭 創建路徑 因此，最長的公共子序列是`CD`。  LCS * * * **在解決 LCS 問題時，動態規劃算法比遞歸算法效率如何？** 動態規劃的方法減少了函數調用的次數。 它存儲每個函數調用的結果，以便可以在以后的調用中使用它，而無需冗余調用。 在上述動態算法中，將從`X`的元素與`Y`的元素之間的每次比較獲得的結果存儲在表中，以便可以在將來的計算中使用。 因此，動態方法所花費的時間就是填寫表格所花費的時間（即`O(mn)`）。 而遞歸算法的復雜度為`2^max(m, n)`。 * * * ## 最長公共子序列算法 ``` X and Y be two given sequences Initialize a table LCS of dimension X.length * Y.length X.label = X Y.label = Y LCS[0][] = 0 LCS[][0] = 0 Start from LCS[1][1] Compare X[i] and Y[j] If X[i] = Y[j] LCS[i][j] = 1 + LCS[i-1, j-1] Point an arrow to LCS[i][j] Else LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]) Point an arrow to max(LCS[i-1][j], LCS[i][j-1]) ``` * * * ## Python，Java 和 C/C++ 示例 ```py # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = [[0 for x in range(n+1)] for x in range(m+1)] # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L[i][j] = 0 elif S1[i-1] == S2[j-1]: L[i][j] = L[i-1][j-1] + 1 else: L[i][j] = max(L[i-1][j], L[i][j-1]) index = L[m][n] lcs_algo = [""] * (index+1) lcs_algo[index] = "" i = m j = n while i > 0 and j > 0: if S1[i-1] == S2[j-1]: lcs_algo[index-1] = S1[i-1] i -= 1 j -= 1 index -= 1 elif L[i-1][j] > L[i][j-1]: i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "\nS2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n) ``` ```java // The longest common subsequence in Java class LCS_ALGO { static void lcs(String S1, String S2, int m, int n) { int[][] LCS_table = new int[m + 1][n + 1]; // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) LCS_table[i][j] = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1; else LCS_table[i][j] = Math.max(LCS_table[i - 1][j], LCS_table[i][j - 1]); } } int index = LCS_table[m][n]; int temp = index; char[] lcs = new char[index + 1]; lcs[index] = '\0'; int i = m, j = n; while (i > 0 && j > 0) { if (S1.charAt(i - 1) == S2.charAt(j - 1)) { lcs[index - 1] = S1.charAt(i - 1); i--; j--; index--; } else if (LCS_table[i - 1][j] > LCS_table[i][j - 1]) i--; else j--; } // Printing the sub sequences System.out.print("S1 : " + S1 + "\nS2 : " + S2 + "\nLCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs[k]); System.out.println(""); } public static void main(String[] args) { String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); } } ``` ```c // The longest common subsequence in C #include <stdio.h> #include <string.h> int i, j, m, n, LCS_table[20][20]; char S1[20] = "ACADB", S2[20] = "CBDA", b[20][20]; void lcsAlgo() { m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table[i][0] = 0; for (i = 0; i <= n; i++) LCS_table[0][i] = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (S1[i - 1] == S2[j - 1]) { LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1; } else if (LCS_table[i - 1][j] >= LCS_table[i][j - 1]) { LCS_table[i][j] = LCS_table[i - 1][j]; } else { LCS_table[i][j] = LCS_table[i][j - 1]; } } int index = LCS_table[m][n]; char lcsAlgo[index + 1]; lcsAlgo[index] = '\0'; int i = m, j = n; while (i > 0 && j > 0) { if (S1[i - 1] == S2[j - 1]) { lcsAlgo[index - 1] = S1[i - 1]; i--; j--; index--; } else if (LCS_table[i - 1][j] > LCS_table[i][j - 1]) i--; else j--; } // Printing the sub sequences printf("S1 : %s \nS2 : %s \n", S1, S2); printf("LCS: %s", lcsAlgo); } int main() { lcsAlgo(); printf("\n"); } ``` ```cpp // The longest common subsequence in C++ #include <iostream> using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) { int LCS_table[m + 1][n + 1]; // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) LCS_table[i][j] = 0; else if (S1[i - 1] == S2[j - 1]) LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1; else LCS_table[i][j] = max(LCS_table[i - 1][j], LCS_table[i][j - 1]); } } int index = LCS_table[m][n]; char lcsAlgo[index + 1]; lcsAlgo[index] = '\0'; int i = m, j = n; while (i > 0 && j > 0) { if (S1[i - 1] == S2[j - 1]) { lcsAlgo[index - 1] = S1[i - 1]; i--; j--; index--; } else if (LCS_table[i - 1][j] > LCS_table[i][j - 1]) i--; else j--; } // Printing the sub sequences cout << "S1 : " << S1 << "\nS2 : " << S2 << "\nLCS: " << lcsAlgo << "\n"; } int main() { char S1[] = "ACADB"; char S2[] = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); } ``` * * * ## 最長的公共子序列應用 1. 在壓縮基因組重排數據中 2. 通過空中簽名在手機中驗證用戶身份