最长公共子序列

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

但在我们理解问题之前，让我们先了解术语子序列是什么 -

让我们考虑一个序列 S = <s ₁ , s ₂ , s ₃ , s ₄ , …,s _n > 。S 上的另一个序列 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-1, j] 和 T[i, j-1] 之间的最大值来填充T[i，j]。

步骤 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。

分析

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

例子

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

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];
    // 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)
          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("\nLength 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-utility 等数据比较程序的基础，并且在生物信息学中具有应用。它还被版本控制系统（例如 SVN 和 Git）广泛使用，用于协调对版本控制的文件集合所做的多个更改。