最长公共子序列算法
最长公共子序列问题是找出同时存在于两个给定字符串中的最长序列。
但在理解这个问题之前，让我们先了解一下"子序列"的含义 −
考虑一个序列 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 − 第 0 行和第 0 列必须用零填充。其余值根据不同情况通过维护计数器值进行填充。
情况 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 表
在下表中，第 0 行和第 0 列均填充为零。剩余值通过递增和根据算法选择最大值来填充。
值填充完成后，从表中 T[4, 5] 处的最后一个值回溯路径。
从回溯路径中，通过选择计数器首次递增的值来找到最长公共子序列。
在本例中，最终计数为 3，因此计数器在 3 个位置递增，即 B、C、B。因此，序列 X 和 Y 的最长公共子序列是 BCB。
实现
以下是最终实现使用动态规划方法实现查找最长公共子序列 −
#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
", 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
", 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
", 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
", 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-utility 等数据比较程序的基础，并且在生物信息学中也有应用。它也被 SVN 和 Git 等版本控制系统广泛用于协调对受版本控制的文件集合所做的多个更改。
