2025年最长公共子序列

最长公共子序列最长公共子序列 英文缩写为 LCS Longest Common Subsequence 其定义是 一个序列 S 如果分别是两个或多个已知序列的子序列 且是所有符合此条件序列中最长的 则 S 称为已知序列的最长公共子序列 子串 子序列还有公共子序列的概念 在上篇 LIS 中也曾涉及过

大家好,我是讯享网,很高兴认识大家。

最长公共子序列,英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

子串、子序列还有公共子序列的概念(在上篇LIS中也曾涉及过) ,我们以字符子串和字符子序列为例,更为形象,也能顺带着理解字符的子串和子序列:

 (1)字符子串:指的是字符串中连续的n个字符,如abcdefg中,ab,cde,fg等都属于它的字串。 ​ (2)字符子序列:指的是字符串中不一定连续但先后顺序一致的n个字符,即可以去掉字符串中的部分字符,但不可改变其前后顺序。如abcdefg中,acdg,bdf属于它的子序列,而bac,dbfg则不是,因为它们与字符串的字符顺序不一致。 ​   (3) 公共子序列:如果序列C既是序列A的子序列,同时也是序列B的子序列,则称它为序列A和序列B的公共子序列。如对序列 1,3,5,4,2,6,8,7和序列 1,4,8,6,7,5 来说,序列1,8,7是它们的一个公共子序列。 ​   那么现在,我们再通俗的总结一下最长公共子序列(LCS):就是A和B的公共子序列中长度最长的(包含元素最多的)

讯享网

其实从上面的对比,我们不难发现公共子序列不严格要求其公共部分是连续的,只要其出现的先后顺序是一致即可,同上方1,3,5,4,2,6,8,7和序列1,4,8,6,7,5;序列1,8,7都是1先出现,8后出现,7最后出现。

仍然用序列1,3,5,4,2,6,8,7和序列1,4,8,6,7,5为例,它们的最长公共子序列有1,4,8,7和1,4,6,7两种,但最长公共子序列的长度是4。由此可见,最长公共子序列(LCS)也不一定唯一。

动态规划解决最长子序列思路

概念描述:

讯享网解决LCS问题,需要把原问题分解成若干个子问题,所以需要刻画LCS的特征。       设A=“a0,a1,…,am”,B=“b0,b1,…,bn”,且Z=“z0,z1,…,zk”为它们的最长公共子序列。不难证明有以下性质:             如果am=bn,则zk=am=bn,且“z0,z1,…,z(k-1)”是“a0,a1,…,a(m-1)”和“b0,b1,…,b(n-1)”的一个最长公共子序列;       如果am!=bn,则若zk!=am,蕴涵“z0,z1,…,zk”是“a0,a1,…,a(m-1)”和“b0,b1,…,bn”的一个最长公共子序列;       如果am!=bn,则若zk!=bn,蕴涵“z0,z1,…,zk”是“a0,a1,…,am”和“b0,b1,…,b(n-1)”的一个最长公共子序列。

对应图解:

img
讯享网

假如S1的最后一个元素与S2的最后一个元素相等,那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS 再加上 S1和S2相等的最后一个元素。

假如S1的最后一个元素与S2的最后一个元素不等(本例子就是属于这种情况),那么S1和S2的LCS就等于 : {S1减去最后一个元素} 与 S2 的LCS, {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。

引进一个二维数组c[ ] [ ],用记录X[ i ]与Y[ j ]的LCS 的长度,b[ i ] [ j ]记录c[ i ] [ j ]是通过哪一个子问题的值求得的,以决定搜索的方向。 我们是自底向上进行递推计算,那么在计算c[i,j]之前,c[ i - 1 ] [ j - 1 ],c[ i - 1 ] [ j ]和c[ i ] [ j - 1 ]均已计算出来。此时我们根据X[ i ]==Y[ j ]还是X[ i ]!=Y[ j ],就可以计算出c[ i ] [ j ]。递推公式如下:

代码思路整合:

如下图,也正是由于在求解过程当中,有些步骤的结果会被反复使用,这也就是为什么使用动态规划建立表格,以空间换取时间的办法

建立二维数组及分析字符的比较情况

二维数组初始情况及转移方程(也就是填写记录表的情况)

填写dp表格的两种情况:

 dp表格填写过程说明:

如填写dp[2] [2]时,X[2-1] = b与Y[2-1] = c不相等,就是选择第二种情况,选择其左、上格子较大值填入,发现都是1,填入1;

 如填写dp[3] [2]时,X[3-1] = c与Y[2-1] = c相等,就是选择第一种情况,选择其dp[i-1] [j-1]填入,发现是1,填入1+1=2;

 最终结果:

代码:

#define Max 51//字符的最大个数 int m,n; char a[m],b[n];//两个字符数组 int dp[Max][Max];//动态规划数组 char subs[Max];//存放LCS void LCSLength()//求dp的过程 { int i,j; for (i = 0; i <= m; i++)//边界条件,将dp[i][0]也就是第一列全置为0 dp[i][0] = 0; for (j = 0; j<= n; j++)//边界条件,将dp[0][j]也就是第一行全置为0 dp[0][j] = 0; for (i = 1; i <= m; i++)//问题规模m*n { for (j = 1; j<= n; j++) { if (a[i-1] == b[j-1])//第一种情况,两个序列最后的一个字符相等 dp[i][j] = dp[i-1][j-1] + 1; else//第二种情况,两个序列最后一个字符不相等 dp[i][j] = max(dp[i-1][j],dp[i][j-1]);//将该结点的左、上结点比较,将更大的值填入该结点 } } }

那么到了这里我们只是填好了dp表格,但是我们要怎么样根据这个表格得到我们想要的LCS序列字符数组呢?

原理:由于我们填表的时候,当找到一个公共字符我们就会将dp[i] [j]的值设置为dp[i-1] [j-1] + 1的值,那么这个值也就是我们根据dp表找公共子序列的那个字符

 寻找字符的过程:

 

 最终情况:

回溯输出最长公共子序列过程:

对应代码:  

讯享网void BuildSubs() { int k = dp[m][n];//填完了dp表之后,dp最右下角的那个数值就是子序列的最大长度 int i = m,j = n; int len = 1; while (k > 0)//子序列长度大于0时,在subs中放入最长公共子序列(反向) { if (dp[i][j] == dp[i-1][j])//与上方元素不相等,往上方回溯可能会遇见子序列 i--; else if (dp[i][j] == dp[i][j-1])//与左方元素不相等,往左方回溯可能会遇见子序列 j--; else//与上方、左给、方元素均不相等,即填表时X[i]==Y[j]遇见了子序列情况 { subs[len++] = a[i-1];//subs中添加公共字符 i--; j--; k--; } } }

 或者直接整合代码:

#include <stdio.h> #include <string.h> #define MAXLEN 51 void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]) { int i, j; for (i = 0; i <= m; i++) c[i][0] = 0; for (j = 1; j <= n; j++) c[0][j] = 0; for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) { if (x[i - 1] == y[j - 1]) { c[i][j] = c[i - 1][j - 1] + 1; b[i][j] = 0;//为了后面回溯,作为公共子序列的判定 } else if (c[i - 1][j] >= c[i][j - 1]) { c[i][j] = c[i - 1][j]; b[i][j] = 1;//为了后面向上回溯,向上寻找子序列的判定 } else { c[i][j] = c[i][j - 1]; b[i][j] = -1;//为了后面向左回溯,向左寻找子序列的判定 } } } } void PrintLCS(int b[][MAXLEN], char *x, int i, int j) { if (i == 0 || j == 0) return; if (b[i][j] == 0)//找到了公共字符 { PrintLCS(b, x, i - 1, j - 1); printf("%c ", x[i - 1]); } else if (b[i][j] == 1)//向上回溯的过程 PrintLCS(b, x, i - 1, j); else//向左回溯的过程 PrintLCS(b, x, i, j - 1); } int main(int argc, char argv) { char x[MAXLEN] = { "ABCBDAB" }; char y[MAXLEN] = { "BDCABA" }; int b[MAXLEN][MAXLEN]; int c[MAXLEN][MAXLEN]; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b);//填写动态规划表格 PrintLCS(b, x, m, n);//回溯输出最长公共子序列 return 0; }

部分文档参考:

BiliBili侠姐聊算法

程序员编程艺术第十一章:最长公共子序列(LCS)问题_v_JULY_v的博客-CSDN博客

部分图片引用:

(1条消息) 动态规划 最长公共子序列 过程图解_Running07的博客-CSDN博客_最长公共子序列

鉴于个人见解整个代码以及动态规划的过程希望能帮助大家理解,制作不易

小讯
上一篇 2025-02-24 16:45
下一篇 2025-03-01 09:28

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/113646.html