最长公共子序列算法

Table of content
上一页
下一页

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

但在我们理解这个问题之前，让我们先了解一下子序列的含义：

让我们考虑一个序列S = <s1, s2, s3, s4, …,sn>。另一个序列Z = <z1, z2, z3, …,zm> 在S上被称为S的子序列，当且仅当它可以通过删除S中的一些元素得到。简单来说，子序列由构成序列一部分的连续元素组成。

公共子序列

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

最长公共子序列

如果给定一组序列，最长公共子序列问题就是找到所有序列的公共子序列中长度最大的一个。

朴素方法

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

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

最长公共子序列算法

设X=<x1,x2,x3....,xm> 和 Y=<y1,y2,y3....,ym> 为序列。为了计算一个元素的长度，使用以下算法。

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

在下表中，第零行和第零列填充为零。其余值根据算法递增和选择最大值来填充。

table1

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

table2

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

在这个例子中，最终计数是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];
    // 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("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）中，用于协调对版本控制的文件集合所做的多个更改。

打印页面
上一页
下一页
广告