LCS(Longest Common Subsequence)最长公共子序列
2024-10-08 14:24:22
最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是:子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题,也是数据比较程序,比如Diff工具,和生物信息学应用的基础。它也被广泛地应用在版本控制,比如Git用来调和文件之间的改变。
最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是连续的。
定义:一个数列,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则称为已知序列的最长公共子序列。
两个序列的解法
最长公共子序列问题存在最优子结构:这个问题可以分解成更小,更简单的“子问题”,这个子问题可以分成更多的子问题,因此整个问题就变得简单了。最长公共子序列问题的子问题的解是可以重复使用的,也就是说,更高级别的子问题通常会重用低级子问题的解。拥有这个两个属性的问题可以使用动态规划算法来解决,这样子问题的解就可以被储存起来,而不用重复计算。这个过程需要在一个表中储存同一级别的子问题的解,因此这个解可以被更高级的子问题使用。
核心数组表示{\displaystyle X}的第位和{\displaystyle Y}的第{\displaystyle j}位之前的最长公共子序列的长度,则有状态转移方程:
当x[i+1]==y[j+1]时,f[i+1][j+1]=f[i][j]+1;//比之前多了一个
否则f[i+1][j+1]=max(f[i][j + 1],f[i + 1][j]);
最新文章
- 引入DecimalFormat类进行数字格式化操作
- MySQL 权限
- mysqldump: Got error: 1142: SELECT, LOCK TABLES command denied to user 'root'@'localhost' for table 'accounts' when using LOCK TABLES
- [转载]彻底弄清struct和typedef struct
- IE11和传统asp.net的兼容问题
- DevExpress GridControl 使用方法技巧 总结 收录整理
- 软件测试技术(二)——使用等价类划分的方法进行的UI测试
- (转载)JavaScript中的Window窗口对象
- jQuery遍历-后代
- lintcode.22 平面列表
- Maven项目构建管理
- Python动态绑定属性slots的使用
- Linux多线程编程,为什么要使用线程,使用线程的理由和优点等
- C# Window Service安装、卸载、恢复选项操作
- kubernetes集群搭建(6):kubernetes基本使用演示
- .Net修改网站项目调试时的虚拟目录
- cf 290F. Treeland Tour 最长上升子序列 + 树的回溯 难度:1
- Linux命令应用大词典-第13章 用户和组群管理
- iOS:操作队列实现多线程NSOperation
- 关于SIM800C MINI V4.0 V4版本 5v供电模块重启问题