程序员的算法课(6)-最长公共子序列(LCS)

时间:2024-09-20 19:06:50
版权声明:本文为博主原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。

上一节我们讲了动态规划,我们也知道,动态规划对于子问题重叠的情况特别有效,因为它将子问题的解保存在存储空间中,当需要某个子问题的解时,直接取值即可,从而避免重复计算!

这一节我们来解决一个问题,就是最长公共子序列。

一、啥叫最长公共子序列?

【百度百科】LCS是Longest Common Subsequence的缩写,即最长公共子序列。一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则为最长公共子序列

在两个字符串中,有些字符会一样,形成的子序列也有可能相等,因此,长度最长的相等子序列便是两者间的最长公共字序列,其长度可以使用动态规划来求。

比如,对于字符串str1:"aabcd";有顺序且相互相邻的aabc是其子序列,有顺序但是不相邻的abd也是其子序列。即,只要得出序列中各个元素属于所给出的数列,就是子序列。

再来一个字符串str2:"12abcabcd";对比可以得出str1和str2的最长公共子序列是abcd。

得出结论:

  1. 子序列不是子集,它和原始序列的元素顺序是相关的。
  2. 空序列是任何两个序列的公共子序列。
  3. 子序列、公共子序列以及最长公共子序列都不唯一。
  4. 对于一个长度为n的序列,它一共有2^n 个子序列,有(2^n – 1)个非空子序列。

二、P问题和NP问题

P问题:一个问题可以在多项式(O(n^k))的时间复杂度内解决。
NP问题:一个问题的解可以在多项式的时间内被验证。

用人话来解释:

P问题:一个问题可以在多项式(O(n^k))的时间复杂度内解决。
NP问题:一个问题的解可以在多项式的时间内被验证。

三、最长公共子序列的解决办法

PS:可以使用递归去蛮力解决,需要遍历出所有的可能,时间复杂度是O(2^m*2^n),太慢了。

对于一般的LCS问题,都属于NP问题。当数列的量为一定的时,都可以采用动态规划去解决。时间复杂度时O(n * m),空间也是O(n * m)。

1.分析规律

对于可用动态规划求解的问题,一般有两个特征:①最优子结构;②重叠子问题

①最优子结构

设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列,将 X 和 Y 的最长公共子序列记为LCS(X,Y)

找出LCS(X,Y)就是一个最优化问题。因为,我们需要找到X 和 Y中最长的那个公共子序列。而要找X 和 Y的LCS,首先考虑X的最后一个元素和Y的最后一个元素。

1)如果 xn=ym,即X的最后一个元素与Y的最后一个元素相同,这说明该元素一定位于公共子序列中。因此,现在只需要找:LCS(Xn-1,Ym-1)

LCS(Xn-1,Ym-1)就是原问题的一个子问题。为什么叫子问题?因为它的规模比原问题小。(小一个元素也是小嘛....)

为什么是最优的子问题?因为我们要找的是Xn-1 和 Ym-1 的最长公共子序列啊。。。最长的!!!换句话说,就是最优的那个。(这里的最优就是最长的意思)

2)如果xn != ym,这下要麻烦一点,因为它产生了两个子问题:LCS(Xn-1,Ym) 和 LCS(Xn,Ym-1)

因为序列X 和 序列Y 的最后一个元素不相等嘛,那说明最后一个元素不可能是最长公共子序列中的元素嘛。(都不相等了,怎么公共嘛)。

LCS(Xn-1,Ym)表示:最长公共序列可以在(x1,x2,....x(n-1)) 和 (y1,y2,...yn)中找。

LCS(Xn,Ym-1)表示:最长公共序列可以在(x1,x2,....xn) 和 (y1,y2,...y(n-1))中找。

求解上面两个子问题,得到的公共子序列谁最长,那谁就是 LCS(X,Y)。用数学表示就是:

LCS=max{LCS(Xn-1,Ym),LCS(Xn,Ym-1)}

由于条件 1)  和  2)  考虑到了所有可能的情况。因此,我们成功地把原问题 转化 成了 三个规模更小的子问题。

②重叠子问题

重叠子问题是啥?就是说原问题 转化 成子问题后, 子问题中有相同的问题。

来看看,原问题是:LCS(X,Y)。子问题有 ❶LCS(Xn-1,Ym-1)    ❷LCS(Xn-1,Ym)    ❸LCS(Xn,Ym-1)

初一看,这三个子问题是不重叠的。可本质上它们是重叠的,因为它们只重叠了一大部分。举例:

第二个子问题:LCS(Xn-1,Ym) 就包含了:问题❶LCS(Xn-1,Ym-1),为什么?

因为,当Xn-1 和 Ym 的最后一个元素不相同时,我们又需要将LCS(Xn-1,Ym)进行分解:分解成:LCS(Xn-1,Ym-1) 和 LCS(Xn-2,Ym)

也就是说:在子问题的继续分解中,有些问题是重叠的。

2.做法

如果用一个二维数组c表示字符串X和Y中对应的前i,前j个字符的LCS的长度话,可以得到以下公式:

程序员的算法课(6)-最长公共子序列(LCS)

  1. 这个非常好理解,其中一个字符串为0的时候,那么肯定是0了。
  2. 当两个字符相等的时候,这个时候很好理解,举例来说:
  3. abcd 和 adcd,在遍历c的时候,发现前面只有a相等了,也就是1.
  4. 那么c相等,也就是abcadc在匹配的时候,一定比abad的长度大1,这个1就是c相等么。也就是相等的时候,是比c[i-1][j-1]1的。
  5. 下一个更好理解了,如果不相等,肯定就是找到上一个时刻对比最大的么。

因此,我们只需要从c[0][0]开始填表,填到c[m-1][n-1],所得到的c[m-1][n-1]就是LCS的长度。

但是,我们怎么得到LCS本身而非LCS的长度呢?也是用一个二维数组b来表示:

  • 在对应字符相等的时候,用↖标记
  • 在p1 >= p2的时候,用↑标记
  • 在p1 < p2的时候,用←标记

标记函数为:

程序员的算法课(6)-最长公共子序列(LCS)

比如说求ABCBDAB和BDCABA的LCS:

程序员的算法课(6)-最长公共子序列(LCS)

灰色且带↖箭头的部分即为所有的LCS的字符。就是一个填表过程。填好的表也就把子序列记录下来了,我们可以通过查表的方式得到你要的最长子序列。

这里可以看到,我们构造的一个i*j的矩阵,这个矩阵里的内容不但包括数值(当前结果的最优解),还包括一个方向箭头,这个代表了我们回溯的时候,需要行走的方向。

所以我们这里保存两个值,可以使用两个二维矩阵,也可以使用一个结构体矩阵。

四、演示下c数组的填表过程

以求ABCB和BDCA的LCS长度为例:

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

程序员的算法课(6)-最长公共子序列(LCS)

以此类推

最后填出的表为:

程序员的算法课(6)-最长公共子序列(LCS)

右下角的2即为LCS的长度。

五、实现代码

 
public class LongestCommonSubsequence {
public static int [][]mem;
public static int [][]s;
public static int [] result; // 记录子串下标
public static int LCS(char []X,char []Y,int n,int m){
for (int i = 0; i <= n; i++) {
mem[i][0] = 0;
s[i][0] = 0;
}
for (int i = 0; i <= m; i++) {
mem[0][i] = 0;
s[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m ; j++) {
if (X[i-1] == Y[j-1]){
mem[i][j] = mem[i-1][j-1] + 1;
s[i][j] = 1;
}
else {
mem[i][j] = Math.max(mem[i][j-1],mem[i-1][j]);
if (mem[i][j] == mem[i-1][j]){
s[i][j] = 2;
}
else s[i][j] = 3;
}
}
}
return mem[n][m];
}
// 追踪解
public static void trace_solution(int n,int m){
int i = n;
int j = m;
int p = 0;
while (true){
if (i== 0 || j == 0) break;
if (s[i][j] == 1 ){
result[p] = i;
p++;
i--;j--;
}
else if (s[i][j] == 2){
i--;
}
else { //s[i][j] == 3
j--;
}
} }
public static void print(int [][]array,int n,int m){
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < m + 1; j++) {
System.out.printf("%d ",array[i][j]);
}
System.out.println();
}
} public static void main(String[] args) {
char []X = {'A','B','C','B','D','A','B'};
char []Y = {'B','D','C','A','B','A'};
int n = X.length;
int m = Y.length;
// 这里重点理解,相当于多加了第一行 第一列。
mem = new int[n+1][m+1];
// 1 表示 左上箭头 2 表示 上 3 表示 左
s = new int[n+1][m+1];
result = new int[Math.min(n,m)];
int longest = LCS(X,Y,n,m);
System.out.println("备忘录表为:");
print(mem,n,m);
System.out.println("标记函数表为:");
print(s,n,m);
System.out.printf("longest : %d \n",longest); trace_solution(n,m);
// 输出注意 result 记录的是字符在序列中的下标
for (int k = longest-1; k >=0 ; k--) {
// 还需要再减一 才能跟 X Y序列对齐。
int index = result[k]-1;
System.out.printf("%c ",X[index]);
} }
}
备忘录表为:
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 1 1 1 1 2 2
0 1 1 2 2 2 2
0 1 1 2 2 3 3
0 1 2 2 2 3 3
0 1 2 2 3 3 4
0 1 2 2 3 4 4
标记函数表为:
0 0 0 0 0 0 0
0 2 2 2 1 3 1
0 1 3 3 2 1 3
0 2 2 1 3 2 2
0 1 2 2 2 1 3
0 2 1 2 2 2 2
0 2 2 2 1 2 1
0 1 2 2 2 1 2
longest : 4
B C B A

六、总结

感觉没有讲到位,先挖坑在这里吧。

  1. 需要两个数组分别保存长度和具体的最长公共子序列的值
  2. 通过二维表的方式,把上一个结果存起来,后面只要查表就可以了
  3. git的diff算法是对最长公共子序列算法的延伸,性能更高

我的微信公众号:架构真经(id:gentoo666),分享Java干货,高并发编程,热门技术教程,微服务及分布式技术,架构设计,区块链技术,人工智能,大数据,Java面试题,以及前沿热门资讯等。每日更新哦!

程序员的算法课(6)-最长公共子序列(LCS)

参考资料:

  1. https://www.jianshu.com/p/cffe6217e13b
  2. https://blog.****.net/lz161530245/article/details/76943991
  3. https://www.cnblogs.com/xujian2014/p/4362012.html
  4. https://www.cnblogs.com/wkfvawl/p/9362287.html
  5. https://www.jianshu.com/p/b0172a3ac46c
  6. https://blog.****.net/weixin_40673608/article/details/84262695
  7. git diff比较
  8. https://blog.****.net/lxt_lucia/article/details/81209962
  9. https://blog.****.net/smilejiasmile/article/details/81503537