动态规划---求最长公共子序列和最长公共子串(C语言)
发布日期:2021-11-15 21:44:09 浏览次数:1 分类:技术文章

本文共 2179 字,大约阅读时间需要 7 分钟。

参考:

一、求最长公共子序列

1、问题描述:

从一个给定的串中删去(不一定连续地删去)0个或0个以上的字符,剩下地字符按原来顺序组成的串。例如:“ ”,“a”,“xb”,“aaa”,“bbb”,“xabb”,“xaaabbb”都是串“xaaabbb”的子序列。(例子中的串不包含引号。)

要求:给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn},找出X和Y的最长公共子序列。

输入:输入数据有多组,每组有两行 ,每行为一个长度不超过500的字符串(输入全是大写英文字母(A,Z)),表示序列X和Y。

输出:每组输出一行,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输出0。

样例输入:

13456778
357486782

样例输出:

5

1、暴力解法:

假设 m<n, 对于母串X,我们可以暴力找出2的m次方个子序列,然后依次在母串Y中匹配,算法的时间复杂度会达到指数级O(n∗2的m次)。显然,暴力求解不太适用于此类问题。

2、递归求解:

当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时,必须解两个子问题,即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。
在算法LCS中,每一次的递归调用使i或j减1,因此算法的计算时间为O(m+n)。

3、动态规划:

(1)创建DP数组C[ ] [ ]
在插入图片描述
(2)把首行和首列置零
在这里插入图片描述
(3)按照以下规则把表填满
在这里插入图片描述
在这里插入图片描述
C[8][9]=5即为所要求的最长公共子序列的长度

代码如下:

#include
#include
int max(int a,int b){
return a>b?a:b;}int main(){
int i,j,k; char a[600]; char b[600]; int f[600][600]; while(scanf("%s %s",a,b)!=EOF) {
int n=strlen(a); int m=strlen(b); for(i=0;i<=n;i++) {
f[i][0]=0; } for(i=0;i<=m;i++) {
f[0][i]=0; } for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
if(a[i-1]==b[j-1]) {
f[i][j]=f[i-1][j-1]+1; } else {
f[i][j]=max(f[i-1][j],f[i][j-1]); } } } printf("%d\n",f[n][m]); } return 0;}

S1和S2的最LCS并不是只有1个,本文并不是着重讲输出两个序列的所有LCS,只是介绍如何通过上表,输出其中一个LCS。

我们根据递归公式构建了上表,我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。
c[8][9] = 5,且S1[8] != S2[9],所以倒推回去,c[8][9]的值来源于c[8][8]的值(因为c[8][8] > c[7][9])。
c[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去,c[8][8]的值来源于 c[7][7]。
以此类推,如果遇到S1[i] != S2[j] ,且c[i-1][j] = c[i][j-1] 这种存在分支的情况,这里请都选择一个方向(之后遇到这样的情况,也选择相同的方向)

第一种结果为:

在这里插入图片描述

这就是倒推回去的路径,棕色方格为相等元素,即LCS = {3,4,6,7,8},这是其中一个结果。

如果如果遇到S1[i] != S2[j] ,且c[i-1][j] = c[i][j-1] 这种存在分支的情况,选择另一个方向,会得到另一个结果。

在这里插入图片描述
即LCS ={3,5,7,7,8}。

二、DP求解最长公共子串

前面提到了子串是一种特殊的子序列,因此同样可以用DP来解决。定义数组的存储含义对于后面推导转移方程显得尤为重要,糟糕的数组定义会导致异常繁杂的转移方程。考虑到子串的连续性,将二维数组c[i][j]用来记录具有这样特点的子串——结尾同时也为为串x1x2⋯xi与y1y2⋯yj的结尾——的长度。

得到转移方程:
在这里插入图片描述
最长公共子串的长度为 max(c[i,j]), i∈{1,⋯,m},j∈{1,⋯,n}。

转载地址:https://blog.csdn.net/qq_43419016/article/details/89255931 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:二叉树的基本操作(C语言)
下一篇:快排函数qsort(C语言)

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月05日 22时05分46秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

云麦小米华为体脂秤怎么样_云康宝和华为智能体脂秤对比评测,实际体验告诉你哪款更好... 2019-04-21
linux 条件判断 取非_Linux awk 系列文章之 awk 多重条件判断 2019-04-21
c语言中如何将字符串的元素一个一个取出_C语言中常用的字符串操作函数 2019-04-21
2d游戏地图编辑器_王者荣耀:新版本爆料!地图编辑器“天工”即将开测,游戏怎么玩由你定!... 2019-04-21
.net framework服务启动后停止_dos命令net图文教程,start启动系统服务stop停止服务批处理脚本... 2019-04-21
8k分辨率需要多大带宽_超乎想象!用RTX3080显卡连索尼8K电视玩游戏感受如何?... 2019-04-21
win10怎么开启aptx_Win10未来的黑科技?微软SurfaceFleet大曝光 2019-04-21
creo视图管理器使用方法_学以致用之中望3D—浅谈使用中望3D的初步感受 2019-04-21
周育如的音标口诀大全_花鸟画口诀大全,实用! 2019-04-21
心电图计算心率公式_医学常用的计算公式口诀(内外妇儿),赶快收藏! 2019-04-21
select 移动端 第一个无法选中_Python爬虫微博(移动端)评论 2019-04-21
华为云welink成像是反的_华为发布智能办公神器WeLink,可连接会议室开会,还可一键遥控报销和智能翻译... 2019-04-21
唱好铁血丹心谐音正规_趙贤典:打好“感情牌” 唱好“大合唱” 2019-04-21
aix系统vi修改命令_Linux基础知识必备:利用vi编辑器创建和编辑正文文件 2019-04-21
天涯明月刀开发_玩家被天涯明月刀手游“冷落”?六大门派角色竟不带正眼看人... 2019-04-21
this指向undefined uiapp_一个this都没有,真好 2019-04-21
add p4 多个文件_2-3【微信小程序全栈开发课程】index页面完善--vue文件代码解析... 2019-04-21
5w2h原则指的是什么_什么是5W2H分析法?一首小诗带入进入大门。 2019-04-21
技校毕业是什么学历_中等职业学校是什么_中等职业学校毕业是什么学历 2019-04-21
2压缩备份数据库_MySQL数据备份与恢复(二) xtrabackup工具 2019-04-21