最长公共子序列算法

最长公共子序列算法
实现
应用

上一个

测验

下一个

最长公共子序列问题是要找到同时存在于两个给定字符串中的最长序列。

在理解这个问题之前，让我们先了解什么是子序列 —

考虑一个序列 S = <s₁, s₂, s₃, s₄, ..., s_n>。另一个序列 Z = <z₁, z₂, z₃, ..., z_m> 是 S 的子序列，当且仅当它可以通过从 S 中删除某些元素得到。在简单的话语中，子序列是由序列中连续的元素组成的一个小部分。

公共子序列

假设，X 和 Y 是有限元素集上的两个序列。我们可以说 Z 是 X 和 Y 的公共子序列，如果 Z 同时是 X 和 Y 的子序列。

最长公共子序列

如果给出了一组序列，最长公共子序列问题就是要找到所有这些序列的公共子序列中长度最长的那个。

朴素方法

让 X 是一个长度为 m 的序列，Y 是一个长度为 n 的序列。检查 X 的每一个子序列是否是 Y 的子序列，并返回找到的最长公共子序列。

X 有 2^m 个子序列。测试一个序列是否是 Y 的子序列需要 O(n) 时间。因此，朴素算法的时间复杂度为 O(n2^m)。

最长公共子序列算法

设 X=<x₁,x₂,x₃....,x_m> 和 Y=<y₁,y₂,y₃....,y_m> 为两个序列。为了计算一个元素的长度，使用以下算法。

步骤 1 − 构造一个大小为 n × m 的空邻接表，其中 n = 序列 X 的大小，m = 序列 Y 的大小。表中的行代表序列 X 中的元素，列代表序列 Y 中的元素。

步骤 2 − 第零行和第零列必须填充为零。其余值根据不同情况填充，同时维护一个计数器值。

情况 1 − 如果计数器在 X 和 Y 序列中遇到公共元素，则将计数器加 1。
情况 2 − 如果计数器在 T[i, j] 处未遇到 X 和 Y 序列中的公共元素，则在 T[i, j] 中填充 T[i-1, j] 和 T[i, j-1] 中的最大值。

步骤 3 − 表填充完成后，从表中的最后一个值开始回溯。这里通过追踪计数器首次增量的地方来完成回溯。

步骤 4 − 通过记录追踪路径中的元素，得到最长公共子序列。

伪代码

在此过程中，按行主序计算表 C[m, n]，并计算另一个表 B[m,n] 以构建最优解。

Algorithm: LCS-Length-Table-Formulation (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
         C[i, j] := C[i - 1, j - 1] + 1
         B[i, j] := D
      else
         if C[i -1, j]  C[i, j -1]
            C[i, j] := C[i - 1, j] + 1
            B[i, j] := U
         else
            C[i, j] := C[i, j - 1] + 1
            B[i, j] := L
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i=0 and j=0
   return
if B[i, j] = D
   Print-LCS(B, X, i-1, j-1)
   Print(xi)
else if B[i, j] = U
   Print-LCS(B, X, i-1, j)
else
   Print-LCS(B, X, i, j-1)

此算法将打印 X 和 Y 的最长公共子序列。

分析

为了填充表，外层 for 循环迭代 m 次，内层 for 循环迭代 n 次。因此，该算法的时间复杂度为 O(m,n)，其中 m 和 n 是两个字符串的长度。

示例

在本示例中，我们有两个字符串 X=BACDB 和 Y=BDCB，用于找出最长公共子序列。

按照算法，我们需要计算表 1 和表 2。

给定 n = X 的长度，m = Y 的长度

X = BDCB, Y = BACDB

构造 LCS 表

在下面的表中，第零行和第零列填充为零。其余值按照算法通过增量和选择最大值来填充。

值填充完成后，从表中最后一个值 T[4, 5] 处开始回溯路径。

从追踪的路径中，通过选择计数器首次增量处的值，找出最长公共子序列。

在本示例中，最终计数为 3，因此计数器在 3 个位置增量，即 B、C、B。因此，序列 X 和 Y 的最长公共子序列为 BCB。

实现

以下是使用动态规划方法求最长公共子序列的最终实现 −

C C++ Java Python

#include <stdio.h>
#include <string.h>
int max(int a, int b);
int lcs(char* X, char* Y, int m, int n){
   int L[m + 1][n + 1];
   int i, j, index;
   for (i = 0; i <= m; i++) {
      for (j = 0; j <= n; j++) {
         if (i == 0 || j == 0)
            L[i][j] = 0;
         else if (X[i - 1] == Y[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];
   char LCS[index + 1];
   LCS[index] = '\0';
   i = m, j = n;
   while (i > 0 && j > 0) {
      if (X[i - 1] == Y[j - 1]) {
         LCS[index - 1] = X[i - 1];
         i--;
         j--;
         index--;
      } else if (L[i - 1][j] > L[i][j - 1])
         i--;
      else
         j--;
   }
   printf("LCS: %s\n", LCS);
   return L[m][n];
}
int max(int a, int b){
   return (a > b) ? a : b;
}
int main(){
   char X[] = "ABSDHS";
   char Y[] = "ABDHSP";
   int m = strlen(X);
   int n = strlen(Y);
   printf("Length of LCS is %d\n", lcs(X, Y, m, n));
   return 0;
}

输出

LCS: ABDHS
Length of LCS is 5

#include <bits/stdc++.h>
using namespace std;
int max(int a, int b);
int lcs(char* X, char* Y, int m, int n){
   int L[m + 1][n + 1];
   int i, j, index;
   for (i = 0; i <= m; i++) {
      for (j = 0; j <= n; j++) {
         if (i == 0 || j == 0)
            L[i][j] = 0;
         else if (X[i - 1] == Y[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];
   char LCS[index + 1];
   LCS[index] = '\0';
   i = m, j = n;
   while (i > 0 && j > 0) {
      if (X[i - 1] == Y[j - 1]) {
         LCS[index - 1] = X[i - 1];
         i--;
         j--;
         index--;
      } else if (L[i - 1][j] > L[i][j - 1])
         i--;
      else
         j--;
   }
   printf("LCS: %s\n", LCS);
   return L[m][n];
}
int max(int a, int b){
   return (a > b) ? a : b;
}
int main(){
   char X[] = "ABSDHS";
   char Y[] = "ABDHSP";
   int m = strlen(X);
   int n = strlen(Y);
   printf("Length of LCS is %d\n", lcs(X, Y, m, n));
   return 0;
}

输出

LCS: ABDHS
Length of LCS is 5

import java.util.*;
public class LCS_ALGO {
    public static int max(int a, int b){
        if( a > b){
            return a;
        }
        else{
            return b;
        }
    }
  static int lcs(char arr1[], char arr2[], int m, int n) {
    int[][] L = new int[m + 1][n + 1];
    // 以自底向上的方式构建矩阵
    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        if (i == 0 || j == 0)
          L[i][j] = 0;
        else if (arr1[i - 1] == arr2[j - 1])
          L[i][j] = L[i - 1][j - 1] + 1;
        else
          L[i][j] = max(L[i - 1][j], L[i][j - 1]);
      }
    }

    int index = L[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 (arr1[i - 1] == arr2[j - 1]) {
        lcs[index - 1] = arr1[i - 1];

        i--;
        j--;
        index--;
      }
      else if (L[i - 1][j] > L[i][j - 1])
        i--;
      else
        j--;
    }
    System.out.print("LCS: ");
    for(i = 0; i<=temp; i++){
        System.out.print(lcs[i]);
    }
    System.out.println();
    return L[m][n];
  }

  public static void main(String[] args) {
    String S1 = "ABSDHS";
    String S2 = "ABDHSP";
    char ch1[] = S1.toCharArray();
    char ch2[] = S2.toCharArray();
    int m = ch1.length;
    int n = ch2.length;
    System.out.println("Length of LCS is: " + lcs(ch1, ch2, m, n));
  }
}

输出

LCS: ABDHS
Length of LCS is: 5

def lcs(X, Y, m, n):
   L = [[None]*(n+1) for a in range(m+1)]
   for i in range(m+1):
      for j in range(n+1):
         if (i == 0 or j == 0):
            L[i][j] = 0
         elif (X[i - 1] == Y[j - 1]):
            L[i][j] = L[i - 1][j - 1] + 1
         else:
            L[i][j] = max(L[i - 1][j], L[i][j - 1])
   l = L[m][n]
   LCS = [None] * (l)
   a = m
   b = n
   while (a > 0 and b > 0):
      if (X[a - 1] == Y[b - 1]):
         LCS[l - 1] = X[a - 1]
         a = a - 1
         b = b - 1
         l = l - 1
      elif (L[a - 1][b] > L[a][b - 1]):
         a = a - 1
      else:
         b = b - 1;
   print("LCS is ")
   print(LCS)
   return L[m][n]

X = "ABSDHS"
Y = "ABDHSP"
m = len(X)
n = len(Y)
lc = lcs(X, Y, m, n)
print("Length of LCS is ")
print(lc)

输出

LCS is 
['A', 'B', 'D', 'H', 'S']
Length of LCS is 
5

应用

最长公共子序列问题是计算机科学中的一个经典问题，是诸如 diff 工具等数据比较程序的基础，并在生物信息学中有应用。它还被版本控制系统（如 SVN 和 Git）广泛用于协调对受版本控制的文件集合所做的多个更改。

笙亿网络策划

数据结构与算法怎么求最长公共子序列LCS？

最长公共子序列算法

公共子序列

最长公共子序列

朴素方法

最长公共子序列算法

伪代码

分析

示例

构造 LCS 表

实现

输出

输出

输出

输出

应用

数据结构与算法怎么求最长公共子序列LCS？

最长公共子序列算法

公共子序列

最长公共子序列

朴素方法

最长公共子序列算法

伪代码

分析

示例

构造 LCS 表

实现

输出

输出

输出

输出

应用

相关问答