算法知识之最长公共子序列问题(动态规划)

article/2025/9/6 15:31:52

最近朋友让帮做个关于动态规划的最长公共子序列的问题,翻看以前的笔记并完成该题后,顺便写这样一篇文章,希望对大家有所帮助,同时也帮助自己回顾该知识点.

一.最长公共子序列的定义

子序列:若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij.
公共子序列:给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列.
最长公共子序列:给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列.
如：序列ABCDEF和ADFGH的最长公共子序列为ADF

注意:最长公共子串(Longest Common Substirng)和最长公共子序列(Longest Common Subsequence,简称LCS)的区别为是最长公共子串的串是一个连续的部分,而最长公共子序列则是从不改变序列的顺序,而从序列中去掉任意的元素而获得新的序列;通俗的说就是子串中字符的位置必须是连续的而子序列则可以不必连续.

二.最优子结构性质

设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,则
    (1)若xm=yn,则zk=xm=yn,且z1,z2,…, zk-1是否为x1,x2,…,xm-1和y1,y2,…,yn-1的最长公共子序列.
    (2)若xm≠yn且zk≠xm,则Z是x1,x2,…,xm-1和Y的最长公共子序列.
    (3)若xm≠yn且zk≠yn,则Z是X和y1,y2,…,yn-1的最长公共子序列.

由此可见,2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列.因此,最长公共子序列问题具有最优子结构性质.当问题具有最优子结构性质和子问题重叠性质时就可以用动态规划算法解决该问题.

三.动态规划方法分析

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系.用c[i][j]记录序列和的最长公共子序列的长度.其中,Xi={x1,x2,…,xi},Yj={y1,y2,…,yj}.当i=0或j=0时,空序列是Xi和Yj的最长公共子序列.故此时C[i][j]=0.其它情况下,由最优子结构性质可建立递归关系如下:

其对应的核心代码如下:

//参数:x字符串长度为m y字符串长度为n
void LCSLength(char x[], char y[],int m，int n)
{  /* 计算最长公共子序列的长度 */int L[m][n],i，j;for (i = 0; i <= m; i++) L[i][0] = 0;for (i = 0; i <= n; i++) L[0][i] = 0;for (i = 1; i <= m; i++){for (j = 1; j <= n; j++) {if (x[i]==y[j]) L[i][j]=L[i-1][j-1]+1;else if (L[i-1][j]>= L[i][j-1])L[i][j]= L[i-1][j]; else L[i][j]= L[i][j-1];}} return L[m][n];
}

例如:输入字符串“bdcaba”和"abcbdab",求它们的最长公共子序列长度.在《算法设计与分析》课程中我们老师讲述的方法通常是使用动态规划填充表格方法解决.初始时,X字符串的长度为m,Y字符串的长度为n.c[m,n]二位数组如上面递归关系递归,最后的c[m,n]为最大数字即最长公共子序列的长度.

其中从表中找出最长公共子序列的方法

 

     (1) 从(m,n)到(0,0)

 

    (2) 若当前格与左边一格相同,则画" 一";若当前格与上边一格相同,则画"|";上两者都不符合,从当前格到左上格化斜线箭头"\";
    (3) 从当前格向箭头方向前进一格,对此格进行(2)
    (4) 从(m,n)到(0,0)的不同路径中,斜线箭头"\"相对应的格的元素构成最长公共子序列.如图bcbd、bcdb、badb.

四.问题的提出与解决

1.问题

题目:求两个字符串的最长公共子序列的长度.
输入:第一行字符串S1,第二行字符串 S2 (1<=字符串长度<=1000).输出:数字M,为最长公共子序列长度.测试用例如下:
输入
BDCABA
ABCBDAB
输出
4
输入
ABKLMNABCDI
ABCDEFGHIJKLMNOPQRSTUVWXYZ
输出
6

 

2.代码

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int *pln1 , *pln2;
char a[10010] , b[10010];
int main()
{int i , j , lena , lenb ;gets(a);gets(b);lena = strlen(a);lenb = strlen(b);pln1 = (int*)calloc( lenb + 1 , sizeof(int) );memset( pln1 , 0 , sizeof(pln1) );pln2 = (int*)calloc( lenb + 1 , sizeof(int) );memset( pln2 , 0 , sizeof(pln2) );for( i = 1 ; i <= lena ; i++ ){for( j = 1 ; j <= lenb ; j++ ){if( a[i-1] == b[j-1] ){pln2[j] = pln1[j-1] + 1;}elseif( pln1[j] >= pln2[j-1] ){pln2[j] = pln1[j];}else{pln2[j] = pln2[j-1];}}free(pln1);pln1 = pln2;pln2 = (int*)calloc( lenb + 1 , sizeof(int) );memset( pln2 , 0 , sizeof(pln2) );}printf( "%d\n" , pln1[lenb] );return 0;
}

五.问题的升华与解决

1.升华问题

输入:输入文件中的第1行是一个正整数T(0<T<=10),表示有T组测试数据.接下来是每组测试数据的描述,每组测试数据有3行.测试数据的第1行有2个正整数m、n,中间用一个空格隔开(0<m，n<50);第2、3行是长度分别为m、n的2个序列X和Y,每个序列的元素间用一个空格隔开.序列中每个元素由字母、数字等构成.输入直到文件结束

输出:对输入中的每组测试数据,先输出Case #表示第几组数据,在输出最长公共子序列,输出所有的最长公共子序列,并输出动态规划表格c表和b表.(测试用例见结果图)

2.代码

这里涉及到一个新的问题：就是使用上面所叙述的填充表格来实现动态规划,其中c[m,n]记录的是当前序列的最长子序列长度;还需要引用一个吧b[m,n]表来寻找所有最长公共子序列,并把结果存入到result[]数组中.其中最重要的代码就是两个实现的函数,如下:

 

第一个LSCLength函数是求最长公共子序列长度的函数,并在该函数中填充c[m][n]和b[m][n].

 

//函数：计算最优值
//参数：m字符串X长 n字符串Y长 X字符串 Y字符串 b标志数组寻找所有字符串用
int LSCLength( int m, int n, char *X, char *Y, int b[][100] )
{/*计算最长公共子序列的长度*/int num[100][100];int i,j;int sum;/*清零*/for( i=0 ; i<=m ; i++ ){for( j=0 ; j<=n ; j++ ){num[i][j]=0;b[i][j]=0;}} /* 递归结构-动态规划并输出 */for( i=1 ; i<=m ; i++ ){		for( j=1 ; j<=n ; j++ ){if( X[i]==Y[j] ) {num[i][j]=num[i-1][j-1]+1;b[i][j]=1;}else if( num[i-1][j]>num[i][j-1] ) {num[i][j]=num[i-1][j];b[i][j]=2;}else if( num[i-1][j]<num[i][j-1] ){num[i][j]=num[i][j-1];b[i][j]=3;}else {num[i][j]=num[i][j-1];b[i][j]=4;}}	}sum = num[m][n];printf("最长公共子序列的长度：%d\n",sum);//输出c[m][n]表printf("\n");for(i=0;i<=m;i++){for(j=0;j<=n;j++){printf("%d ",num[i][j]);}printf("\n");}//输出b[m][n]表printf("\n");for(i=0;i<=m;i++){for(j=0;j<=n;j++){printf("%d ",b[i][j]);}printf("\n");}return sum;
}

第二个DisplayLSC函数是通过b[m][n]递归计算所有最长公共子序列,并存储至result数组中.

//定义全局变量用于保存结果result 结果个数保存为count
char result[100];
int count=0;//函数：计算所有最长公共子序列
//参数：m字符串X的长度 n字符串Y的长度 b标志数组 current_len当前长度 max_len最长公共子序列长度
void DisplayLSC(int i,int j,char *X,int b[][100],int current_len,int max_len)
{int s;//采用递归的算法求解所有长度if(i==0 || j==0)                 //为0时输出结果并返回{for(s=0;s<max_len;s++){printf("%c ",result[s]);}printf("\n");count++;return;}if(b[i][j]==1){current_len--;result[current_len]=X[i];DisplayLSC(i-1,j-1,X,b,current_len,max_len);}else{if(b[i][j]==2){DisplayLSC(i-1,j,X,b,current_len,max_len);}else{if(b[i][j]==3){DisplayLSC(i,j-1,X,b,current_len,max_len);}else{DisplayLSC(i,j-1,X,b,current_len,max_len);DisplayLSC(i-1,j,X,b,current_len,max_len);}}}
}

3.结果

最后输出的结果如下图所示:

      

希望该文章对大家有所帮组,同时该文章参考了王晓东的《计算机算法设计与分析》,并引用了自己学校的PPT动态规划内容.同时感谢梦醒潇湘love博主的文章,希望大家也可以去见解该文章.
http://blog.chinaunix.net/uid-26548237-id-3374211.html
文章主要是对自己以前学过的知识的巩固以记录,如果有错误或不足之处,希望大家海涵.
(By:Eastmount 2013-11-5 中午3点http://blog.csdn.net/eastmount/)


http://chatgpt.dhexx.cn/article/jDLvqYsS.shtml

相关文章

动态规划篇——最长公共子序列(c++)

动态规划篇——最长公共子序列(c++)

引言&#xff1a;最长公共子序列属于动态规划的基础篇&#xff0c;由字符串的最长公共最序列可以引出很多的问题。 最长子序列详细讲解以及练习题目 需要详细讲解教程的可以观看上面链接的文章&#xff0c;以下是自己做的简单的概括。 一、何为最长公共子序列 A和B的公共子序…
阅读更多...
最长公共子序列（LCS）

最长公共子序列（LCS）

此文全文参考自&#xff1a;https://blog.csdn.net/dq_dm/article/details/45043689&#xff0c;特此感谢&#xff01; 然后自己参考了&#xff1a;http://www.ahathinking.com/archives/115.html 和July的ppt讲义《十分钟搞定LCS》&#xff0c;为表示版权&#xff0c;特地留下…
阅读更多...
动态规划——最长公共子序列

动态规划——最长公共子序列

先来讲解以下什么是最长公共子序列。最长公共子序列不是最长相同字符串&#xff0c;有点相似但不一样&#xff0c;来举个简单的例子&#xff0c;有字符串s1bcdea&#xff0c;s2abce&#xff0c;最长相同字符串是bc&#xff0c;最大公共部分是2&#xff1b;而最长公共子序列则是…
阅读更多...
动态规划---例题2.最长公共子序列问题

动态规划---例题2.最长公共子序列问题

本题与力扣主站1143题相同. 一.问题描述 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 确切地说&#xff0c;若给定序列X<x1, x2,…, xm>&#xff0c;则另一序列Z<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik&g…
阅读更多...
知识图谱本体建模之RDF、RDFS、OWL详解

知识图谱本体建模之RDF、RDFS、OWL详解

&#xff08;一&#xff09;知识图谱本体建模之RDF、RDFS、OWL详解 1.语义网体系 知识图谱于2012年由Google提出&#xff0c;并不是新概念&#xff0c;而是由语义网络(Semantic Network)衍生而来。语义网络由相互连接的节点和边组成&#xff0c;节点表示概念或者对象&#xf…
阅读更多...
OWL本体基础知识

OWL本体基础知识

备注&#xff1a; OWL本体中对象属性和数据属性都可以有进一步的注释属性&#xff0c;被称之为公理 <owl:NamedIndividual rdf:about"http://www.semanticweb.org/bob/ontologies/2022/11/untitled-ontology-20#刘二菲"><like rdf:resource"http://www…
阅读更多...
protege系列（一）：本体开发101：创建第一个本体的指南

protege系列（一）：本体开发101：创建第一个本体的指南

protege作为领域本体编辑工作一直为自然语言处理和语义网、知识图谱等行业人士喜爱&#xff0c;但是还没有比较完整的官方Protege中文文档&#xff0c;本系列旨在通过对protege官方网站上教程等内容的翻译和再现&#xff0c;为广大网友提供一个全面的、权威的protege教程。 本…
阅读更多...
动态本体 palantir

动态本体 palantir

102解析器与106本体耦合&#xff0c;106本体与108数据库耦合&#xff1b; 106本体有一个或多个110对象类型和116属性类型 110对象类型实例化多个112对象 每一个对象有一个或多个属性 116属性类型实例化114A和114B属性 116属性类型有一个或多个118组件&#xff0c;组件有字符串、…
阅读更多...
什么是计算机科学中的“本体论”

什么是计算机科学中的“本体论”

最近看用户画像&#xff0c;里面提到了本体论。故把知乎一个回答放于此地。 一、本体的概念 本体的概念有两层意思&#xff0c;一层是哲学层面的意思&#xff0c;一层是引申到信息科学中的语义层面的意思。 举个最通俗的例子来解释一下这两层意思&#xff0c;我们就拿苹果来举…
阅读更多...
本体建模学习笔记

本体建模学习笔记

目录 1. 语义网 & 语义网络 1.1 链接数据与知识图谱 的区别 1.2 本体构建的两种方式 1.3 知识图谱数据的来源 0. RDF、OWL 与RDFS 0.1 RDF序列化 0.2 关系 / 属性 0.3 RDFS词汇 0.4 本体映射词汇&#xff08;Ontology Mapping&#xff09; 2. Protege实现本体建模…
阅读更多...
知识元与知识本体

知识元与知识本体

元数据&#xff08;Metadata&#xff09;就是“关于数据的数据”,是对数据进行组织和处理的基础。元数据法就是对信息单元及其集合进行规范描述从而形成元数据&#xff0c;并依其将分布式的信息资源整合成有机信息体系的基准、方法和工具。主题词表&#xff1a;也称叙词表。它是…
阅读更多...
本体语言 OWL

本体语言 OWL

万维网本体语言OWL2 文章目录 万维网本体语言OWL2一、引言二、本体语言的需求三、OWL2和RDF/RDFS的兼容性3.1 OWL2 Full&#xff1a;基于RDF的语义3.2 OWL2 DL&#xff1a;直接语义 四、OWL语言五、OWL2 概要六、实验 OWL的构造七、总结 一、引言 通俗的讲&#xff0c;RDF被限…
阅读更多...
本体概述

本体概述

目录1.定义2.本体的目标和作用3.本体构成要素4.领域本体与上层本体5.本体语言6. 构造Ontology 的规则 7.本体在信息检索的应用 1.定义 – 1991/Neches 等&#xff1a;给出构成相关领域词汇的基本术语和关系&#xff0c;以及利用这些术语和关系构成的规定这些词汇外延的规则…
阅读更多...
本体 摘抄笔记

本体 摘抄笔记

一、本体的一些介绍 &#xff08;来源&#xff1a;https://blog.csdn.net/shendeguang/article/details/8241164&#xff09; 1. 本体论语义学的特点&#xff1a; 本体论语义学与其他人工智能理论、自然语言加工系统相比有自己的一些鲜明特点。 其一&#xff0c;它强调对意义…
阅读更多...
图构建：领域本体设计原则与动态本体

图构建：领域本体设计原则与动态本体

图构建&#xff1a;领域本体设计原则与动态本体 前文《思考总结&#xff1a;领域知识图谱平台构建与业务应用》中提到&#xff1a;“本体设计是图应用中的重中之重&#xff0c;一切的图展示、图计算、图分析、图挖掘、图模式匹配…的基础在图构建&#xff0c;而图构建的核心是…
阅读更多...
常用本体建模工具

常用本体建模工具

常用本体建模工具&#xff1a; Apollo、OntoStudio、TopBraid Composer、Semantic Turkey、Knoodl、Chimaera、OliEd、WebODE、Kmgen和DOME Protg Protg[1]是一款由斯坦福大学编写并维护的开源本体建模和编辑工具&#xff0c;其支持Web版本和PC版本&#xff0c;使用OWL语言…
阅读更多...
本体(Ontology)

本体(Ontology)

我是在撰写毕业论文中接触到知识表示方面的内容&#xff0c;有时需要理论与实践相结合&#xff0c;关于这方面的理论知识学习&#xff0c;除了网页资料、书籍、另外推荐一个网站&#xff1a;熊猫学术(https://sc.panda321.com/)&#xff0c;可以查阅很多相关的学术论文&#xf…
阅读更多...
知识图谱初步学习（一）——本体+Protege新手学习

知识图谱初步学习（一）——本体+Protege新手学习

文章目录 前言&#xff08;本体详解&#xff09;1.本体概念2.本体分类3.本体组成4.本体构建方法5.本体构建的原则6.本体应用 一、protege简介二、软件使用步骤1.安装2.使用3.案例 三、问题解决方案汇总 前言&#xff08;本体详解&#xff09; 在开始学习知识图谱的过程中&…
阅读更多...
本体调研

本体调研

1.1本体概念 本体是用于描述一个领域的术语集合&#xff0c;其组织结构是层次结构化的&#xff0c;可以作为一个知识库的骨架和基础。 本体不等同于个体&#xff0c;它是相应领域内公认的概念集合。 1.2 本体分类 依照领域依赖程度: &#xff08;1&#xff09;顶层本体&…
阅读更多...
知识图谱初步学习（零）——本体是什么

知识图谱初步学习（零）——本体是什么

知识图谱初步学习&#xff08;零&#xff09;——本体是什么 文章目录 知识图谱初步学习&#xff08;零&#xff09;——本体是什么前言一、 哲学层面理解二、 引申到语义层面理解三、学术层面四、其他层面- 术语- 语义网 五、本体与类、本源、实体、符号的区别六、用语义三角形…
阅读更多...
推荐文章

Copyright @ 2022~2023