位置:首页 » 技术 » 求两字符串最长公共子序列

求两字符串最长公共子序列

日期:2013-11-01 阅读:0num
Advertisement

这是动态规划法 的典型题目,长度为row和长度为col的两个串,如何求他们的最长公共子序列。这个子序列是可以不连续的。

方法:

1 建立(row+1)*(col+1)的二维表,

2. 初始化其首行首列为零

3. 以m串为行,n串为列,那么可以逐行填写。第一行代表n串的第一个字符和m串比较, 第二行代表n串的第一和第二个字符都和m串比较,以此类推。

4. 如果是相同字符,那么就把[m-1][n-1]+1和[m-1[n]和[m][n-1]比较,填入大数。

5. 如此反复填完表,就可以得到最终结果[m][n]

很难一下子说清楚,这里就弥补一下一般书上都没有的C++程序吧:

#include<iostream>
#include<vector>
#include<string>  

using namespace std;  

class Solution {
public:
    int longestSub(string sa, string sb)
    {
        int row = sa.size();
        int col = sb.size();
        vector<vector<int> > dArray;
        vector<int> rowV(col+1,0);
        for(int i = 0; i<row+1; i++)
        {
            dArray.push_back(rowV);
        }
        for(int r=1; r<row+1; r++)
        {
            for(int c=1; c<col+1; c++)
            {
                dArray[r][c] = max(dArray[r-1][c], dArray[r][c-1]);
                if(sa[r-1]==sb[c-1])
                {
                    dArray[r][c] = max(dArray[r-1][c-1]+1, dArray[r][c]);
                }
                else
                {
                    dArray[r][c] = max(dArray[r-1][c-1], dArray[r][c]);
                }
            }//for(int c=1; c<col+1; c++)
        }//for(int r=1; r<row+1; r++)
        return dArray[row][col];
    }//int longestSub(string sa, string sb)
};  

int main()
{
    string str1("jisnldjife");
    string str2("isdklnige");
    Solution solu;
    cout<<solu.longestSub(str1, str2);
    cout<<endl;
    return 0;
}

求两字符串最长公共子序列的相关内容

相关文章
  • 求两字符串最长公共子序列

    这是动态规划法 的典型题目,长度为row和长度为col的两个串,如何求他们的最长公共子序列.这个子序列是可以不连续的. 方法: 1 建立(row+1)*(col+1)的二维表, 2. 初始化其首行首列为零 3. 以m串为行,n串为列,那么可以逐行填写.第一行代表n串的第一个字符和m串比较, 第二行代表n串的第一和第二个字符都和m串比较,以此类推. 4. 如果是相同字符,那么就把[m-1][n-1]+1和[m-1[n]和[m][n-1]比较,填入大数. 5. 如此反复填完表,就可以得到最终结果[m

  • Advanced Fruits(合并字符串+最长公共子序列应用)hdu1503 +动态规划

    Advanced Fruits Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2173 Accepted Submission(s): 1109 Special Judge Problem Description The company 21st Century Fruits has specialized in creating new

  • 最长公共子序列(Longest-Common-Subsequence,LCS)

    一个字符串S,去掉零个或者多个元素所剩下的子串称为S的子序列.最长公共子序列就是寻找两个给定序列的子序列,该子序列在两个序列中以相同的顺序出现,但是不必要是连续的. 例如序列X=ABCBDAB,Y=BDCABA.序列BCA是X和Y的一个公共子序列,但是不是X和Y的最长公共子序列,子序列BCBA是X和Y的一个LCS,序列BDAB也是. 寻找LCS的一种方法是枚举X所有的子序列,然后注意检查是否是Y的子序列,并随时记录发现的最长子序列.假设X有m个元素,则X有2^m个子序列,指数级的时间,对长序列不

  • 算法导论中怎么求两个字符串的最长公共子序列

    算法导论中如何求两个字符串的最长公共子序列 #include<iostream> #include<string> using namespace std; const int max_length=10; void print(int b[max_length][max_length],string X,int i,int j); void LCS(string X,string Y,int b[max_length][max_length],int m,int n ) { in

  • 动态规划 LCS 求两个序列A,B中全部的最长公共子序列 动态规划 LCS 求两个序列A,B中全部的最长公共子序列

    动态规划 LCS 求两个序列A,B中所有的最长公共子序列 动态规划 求两个序列A,B中所有的最长公共子序列 第一部分.什么是动态规划算法 动态规划一般也只能应用于有最优子结构的问题.最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足, 故有时需要引入一定的近似).简单地说,问题能够分解成子问题来解决. 动态规划算法分以下4个步骤: 1,描述最优解的结构 2,递归定义最优解的值 3,按自底向上的方式计算最优解的值 //此3步构成动态规划解的基础. 4,由计算出的结果构造

  • Java动态规划 兑现最长公共子序列以及最长公共子字符串 Java动态规划 兑现最长公共子序列以及最长公共子字符串

    Java动态规划 实现最长公共子序列以及最长公共子字符串 动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题.简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加. 为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法. [问题] 求两字符序列的最长公共字符子序列 问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)

  • 找工作常识储备(2)-数组字符串那些经典算法:最大子序列和,最长递增子序列,最长公共子串,最长公共子序列,字符串编辑距离,最长不重复子串,最长回文子串 找工作常识储备(2)-数组字符串那些经典算法:最大子序列和,最长递增子序列,最长公共子串,最长公共子序列,字符串编辑距离,最长不重复子串,最长回文子串

    找工作知识储备(2)---数组字符串那些经典算法:最大子序列和,最长递增子序列,最长公共子串,最长公共子序列,字符串编辑距离,最长不重复子串,最长回文子串 作者:寒小阳 时间:2013年9月. 出处:http://blog.csdn.net/han_xiaoyang/article/details/11969497. 声明:版权所有,转载请注明出处,谢谢. 0.前言 这一部分的内容原本是打算在之后的字符串或者数组专题里面写的,但看着目前火热进行的各家互联网公司笔试面试中,出现了其中的一两个内容,

  • (hdu step 3.2.2)Common Subsequence(简略dp:求最长公共子序列的长度) (hdu step 3.2.2)Common Subsequence(简略dp:求最长公共子序列的长度)

    (hdu step 3.2.2)Common Subsequence(简单dp:求最长公共子序列的长度) 在写题解之前给自己打一下广告哈~..抱歉了,希望大家多多支持我在CSDN的视频课程,地址如下: http://edu.csdn.net/course/detail/209 题目: Common Subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total S

  • 【动态规划之】求最长公共子序列有关问题 【动态规划之】求最长公共子序列有关问题

    [动态规划之]求最长公共子序列问题 /** ** [email protected] ** http://blog.csdn.net/MonkeyAndy **/ 首先介绍动态规划方法的相关知识 动态规划方法的基本思想: 分成若干个子问题,先求解子问题,然后根据子问题的解求得原问题的解.经分解得到的子问题往往不是互相独立的.可重复利用! 其核心思想就是分治,分治方法的特点是分解后的子问题相对独立,可以通过简单的合并算法得到原问题的解! 动态规划方法的应用对象: 优化问题: 一个优化问题可能有很多

  • 回文字符串(南阳oj37)(最长公共子序列有关问题)

    回文字符串(南阳oj37)(最长公共子序列问题) 回文字符串 时间限制:3000 ms | 内存限制:65535 KB 难度:4 描述 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如"aba".当然,我们给你的问题不会再简单到判断一个字符串是不是回文字符串.现在要求你,给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成为回文字符串. 输入 第一行给出整数N(0<N<100) 接下来的N行,每行一个字符串,每个字符串长度不超

  • HDU 1243 反恐训练营 (动态规划求最长公共子序列)

    反恐训练营 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3040 Accepted Submission(s): 693 Problem Description 当今国际反恐形势很严峻,特别是美国"9.11事件"以后,国际恐怖势力更是有恃无恐,制造了多起骇人听闻的恐怖事件.基于此,各国都十分担心恐怖势力会对本国社会造成的不稳定,

  • 字符串的最长公共子序列问题

    [cpp] // 最长公共子序列问题.cpp : Defines the entry point for the console application. // /*问题:给出两个字符串,找出它们的最长公共子序列 什么是最长公共子序列? 最长公共子序列,英文缩写为LCS(Longest Common Subsequence). 其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列, 且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列. 而最长公共子串(要求连续)和最长

  • 求解两个序列的全部最长公共子序列(LCSes) 求解两个序列的全部最长公共子序列(LCSes)

    求解两个序列的所有最长公共子序列(LCSes)  摘要 本篇博文提供了实现求解所有最长公共子序列的程序实现,并提供输出所有公共子序列的方法解释,需要具备基础知识是求解一个公共子序列的动态规划方法,请自行查阅相关资料. 题目重述 子序列概念:设X=< x1, x2,┅, xm>,若有1≤i1< i2< ┅ <ik≤m,使得Z=< z1, z2,┅, zk> = < xi1, xi2,┅, xik>,则称Z是X的子序列,记为Z<X. 例如: X=

  • 编了个动态规划求最长公共子序列有关问题,lengthLCS函数中双重for循环中i总是不能到len1(崩了),调了一天没调出来,求编程高人指点!

    编了个动态规划求最长公共子序列问题,lengthLCS函数中双重for循环中i总是不能到len1(崩了),调了一天没调出来,求编程高人指点!!! #include<iostream> #include<cstdlib> #include<cstring> using namespace std; //seeking the longest commen subsequence int lengthLCS(string &s1, int len1, string

  • UVA 10635-Prince and Princess+nlgn求最长公共子序列

    UVA 10635--Prince and Princess+nlgn求最长公共子序列 题目链接:点击进入 刚看到这题目还以为又碰到水题了,结果写了个O(n^2)的代码交上去超时了,才发现n有250*250那么大.后面在网上找到了一个nlgn求最长上升子序列的方法,才过了.这个nlgn算法的主要思想是将最长公共子序列转成最长上升子序列,然后用最长上升子序列nlgn的算法求解.更具体的解释可以参看这篇博文:最长公共子序列(nlogn) 代码如下: #include<iostream> #incl

  • 求解两个序列的所有最长公共子序列(LCSes) 求解两个序列的所有最长公共子序列(LCSes)

     摘要 本篇博文提供了实现求解所有最长公共子序列的程序实现,并提供输出所有公共子序列的方法解释,需要具备基础知识是求解一个公共子序列的动态规划方法,请自行查阅相关资料. 题目重述 子序列概念:设X=,若有1≤i1 = ,则称Z是X的子序列,记为Z 例如: X=, Z=, 则有Z 公共子序列概念:设X,Y是两个序列,则有Z 最长公共子序列:若ZZ?LCS(X , Y). 问题: 最长公共子序列一般可以有多个,求解并输出所有的LCS. 问题分析 求解一个LCS比较容易,但求解所有的LCS比较繁琐

  • 算法系列札记6(动态规划—最长公共子序列/串lcs)

    算法系列笔记6(动态规划-最长公共子序列/串lcs) 子序列要求元素顺序一致就可以了,而字串必须是连续的.如ABCBDAB与BDCABA两个字符串,最长公共子序列有BCBA.BDAB和BCAB, 而最长公共字串只有AB和BD<连续>.当然这里的求解只求一个,但通常是这样直接说求最长公共子串,子序列,准确的应该是之一. 最长公共子序列 法一:穷举法 检查字符串x所有字序列,共有2^m个,检查它是否在y字符串中出现,每个需要O(n),时间复杂度为指数级的. 法二:动态规划(DP) 将两个字符串x[

  • 最长公共子序列,该如何处理

    最长公共子序列 前面有很多人问了最长公共子串的问题 ,但这个不是最长公共子串,而是最长公共子序列. 问题差别在于:子串必须是连续的,但子序列不必. 如:ABCBDAB和BDCABA最长公共子串只能是AB或BD,但最长公共子串是BCBA. 输入两个序列,求最长公共子序列.谢谢! ------解决方案-------------------- [供参考] 一.算法思想 一个给定序列的子序列是在该序列中删去若干元素后得到的序列.给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X

  • 【基础练习题】【线性DP】codevs1408 最长公共子序列(上升)题解

    [基础练习][线性DP]codevs1408 最长公共子序列(上升)题解 这道题目捣鼓了一个小时了终于弄出来咯···怒吼三声:容易吗!文章被盗还是很严重,加版权信息转载请注明出处 [ametake版权所有]http://blog.csdn.net/ametake欢迎来看 题目描述 Description 熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目.小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们要研究最长公共上升子序列了. 小沐沐说,对于两个串A,B,如果它们都包

  • UVA 10723-Cyborg Genes+最长公共子序列变形

    UVA 10723--Cyborg Genes+最长公共子序列变形 题目链接:点击进入 首先对于长度最短的情况是很容易确定的,只需要用两个字符串的长度和减去他们的最长公共子序列长度.然后比较麻烦的就是合乎要求的字符串的个数,其实我们也可以用类似于最长公共子序列的dp来求. 设dp[i][j]表示str1的前i个字符和str2的前j个字符所得到的满足要求的字符串,则如果str[i]==str[j],则dp[i][j]+=dp[i-1][j-1]; 否则就要根据i,j这两个位置上的最长公共子序列长度

最新文章
  • 小米3S手机代号X4开始量产!苹果iPhone6上市时间 小米3S手机代号X4开始量产!苹果iPhone6上市时间

    [iPhone6上市时间 小米3S手机代号为X4?] 百度指数显示小米3s手机的关注度持续上扬,涨幅环比超过苹果iPhone6,然而对于什么时候上市,苹果iPhone6官方依旧淡定,有网友提出:难道苹果公司不担心小米3s.努比亚6X和中兴红牛等抢市场占有率吗?具体详细情况随小编一起来看看吧! 除Android阵营的新款机型外,苹果的下一代iPhone6同样也备受消费者关注,可见其人气依旧不减,虽然新一代iPhone6还未发布就被爆料无数次,但这些爆料的信息是否属实就不得而知了.当然,如果苹果在下

  • 2014美容院给顾客的中秋祝福语短信

    2014美容院给顾客的中秋祝福语短信 1.中秋节,圆圆的月亮天上挂,圆圆的祝福为你画:以快乐为圆心,以好运为半径,以真心为画笔,以思念为颜料,画一个圆圆的幸"弧",愿你财"圆"滚滚,福"圆"滔滔,好运"圆圆"不断,合家幸福康安. 2.中秋节到了,我代表月光一族,祝你:月薪加倍,月月发财,月进斗金,月月有余,住月宫级别墅,吃钻石级月饼,再来一张金卡级月票,提供无限期透支! 3.中秋快到了,我们都会想起每逢佳节倍思亲的诗句,但是在

  • 移轴镜头烧不起 好照片带你体验上帝之眼 移轴镜头烧不起 好照片带你体验上帝之眼

    移轴摄影,泛指使用移轴镜头创作的作品.这种摄影,被称为"上帝之眼",所拍摄的作品就像微缩模型一样,十分特别.通常我们采用移轴镜头来实现这样的效果,移轴镜头本来主要是用来修正以普通广角镜拍照时所产生出的透视问题,主要用于建筑摄影,但后来却被广泛利用来创作变化景深聚焦点位置的摄影作品. 如果偶尔想要尝试移轴效果,使用后期也可以帮你实现.除了熟手们常常运用Photoshop外置滤镜以及在通道中通过绘制模糊蒙版来实现,对于希望在后期模拟移轴效果的用户来说,不妨试试这款简单操作,但是效果出色的软

  • 医院网络营销如何分析竞价关键词

    怎么去分析竞价关键词,相信大部分的竞价人员都会有3个统计,一个是百度统计.另一个是商务通里面的关键词统计 ,还有一个是预约系统里面的关键词统计 .那么怎么去分析这些统计到的关键词呢?下边小脑袋百度竞价助手小编简单和大家分析一下. 1.竞价人员怎样分析竞价关键词 百度统计对于竞价人员来说是一个很好的统计关键词的工具,所以竞价人员要养成一种习惯,习惯性的去分析百度统计,必须跟踪每天.每周.每月流量大的 关键词,排在前10位的最起码要跟踪到,这些关键词很可能就是你大部分消费的情况,这些关键词如果有明显

  • 迄今最完整3D宇宙地图出炉 覆盖3.8亿光年呈现5万星系 迄今最完整3D宇宙地图出炉 覆盖3.8亿光年呈现5万星系

    据悉,科学家绘制了迄今为止绘制的最完整的3D本地宇宙地图,所涵盖的星系最远距地球3.8亿光年.该幅宇宙地图包括了呈现2微米全天巡天计划(以下简称2MASS)在红外线条件下观测到的5万个星系,可帮助科学家了解宇宙如何形成和演变. 地图所用数据来自于托马斯·加莱特,他是广域红外探测器和斯皮策太空望远镜项目的软件工程师,同时还是2MASS项目的科学家.横穿地图中央的黑带受到银河系平面的尘埃阻隔.地图中的每一个点代表一个星系,不同颜色代表不同的对地距离.颜色越蓝,距离地球越进,越红则距离地球越远,红移接

  • 4.7吋iPhone6与主流旗舰机对比图 4.7吋iPhone6与主流旗舰机对比图

    4.7英寸屏幕的iPhone 6会是什么样子?下面就先用模拟图来和主流手机进行一次对比. 先是iPhone 5和iPhone 4s的对比:然后是MOTO X和LG G2 mini,尺寸都是4.7英寸,但是因为MOTO X的比例不同,看起来屏幕高度不同. 接着是两款老款旗舰Android手机,HTC One 和三星S3,屏幕也都是4.7英寸,尺寸看起来非常接近. 接着是屏幕更大的Nexus 5和LG G2,由于Nexus 5和LG G2的屏幕边框都极窄,整个高度还没有iPhone 6高. 最后是与

  • 天天飞车闪退怎么办?闪退解决办法 天天飞车闪退怎么办?闪退解决办法

    天天飞车闪退原因我给大家总结了四种,下面我们来参考下面四种方法解决闪退问题,希望本文章对各位同学会带来帮助哦. 1. 我们先尝试重新安装游戏了,这个可能是游戏本身的问题,如果因为此原因出现闪退应该不至你一个人哦. 2. 手机空间不足或内存不足导致的,这个我们可以退出其它的一些任用程序来试下: 3. 游戏系统的问题,天天飞车能ios系统要求在ios5.5,而安卓系统必须在android2.2系统,否则可能出现版本不兼容导致闪退了: 4. 天天飞车游戏必须是可以联网的,否则也有可能出现闪退情况哦.

  • 公司技术总监与经理工作总结与工作计划2012-2014年

    本文章来给各位同学介绍一篇关于公司技术总监与经理工作总结与工作计划2012-2014年,如果你是这个职位的这篇文章非常不错哦. 2012年终总结 2012年是梦想启航的一年,今年以来,从我的工作职责方面,我很感激公司领导的正确领导,公司各个部门及全体施工工作人员对我的大力支持和帮助.2012年xxxx在长沙正式落地,顺利成立了一个团队,并且吸收了大量的优质人才,特别是我们公司在销售.市场.运营.技术这一块拥有多年丰富经验的人才并取得了一定的成功.这些取得与公司领导的正确领导分不开的. 我工作中不

  • 梦幻西游炼药配方技巧心得分享 梦幻西游炼药配方技巧心得分享

    在梦幻西游手机版的这一款游戏里面,炼药是生活技能中最为实用的,既可以炼制三药进行出售,还可以自己进行使用,但是炼药存在不稳定因素,很多玩家都想炼制大金,今天小编就来给各位玩家们来说说大金的炼药配方与技巧,一起来看看吧. 给各位梦幻西游手机版的玩家们分享一下炼妖配方的一些技巧心得. 分享一览: 关于炼药 大金产出配方:3龙凤之睛+1鹿茸 九转金丹:4个血珊瑚 五龙丹:4个孔雀红 关于重炼: 玩家可以把三药进行再次重练,两个三药可以合成一个随机种类.随机品质的三药(可以和炼制种类一样). 药品的品质

  • WIN7开启AHCI蓝屏解决方法 WIN7开启AHCI蓝屏解决方法

    安装WIN 7时未开启AHCI,BIOS里SATA模式为IDE时,在BIOS里直接改成AHCI模式时,会出现蓝屏现像.(具体开启方式请参看主板.笔记本说明书,或者咨询相关品牌售后) 解决方法: 1:在BIOS里SATA模式为IDE的状态下,进入系统后在运行里输入regedit,打开注册表编辑器,依次打开注册表,修改HKEY_LOCAL_MACHINESystemCurrentControlSetServicesMsahci下的 start ,把数值数据改为0,如图: 2.重新启动,在BIOS里改

热门推荐
  • 魅族新品发布会邀请函:窗花中国结复古风 魅族新品发布会邀请函:窗花中国结复古风 魅族将于1月28日下午2点半在北京国家会议中心举行魅蓝新品·魅族智能生态圈发布会.据称魅族将会在发布会宣布与海尔合作,共同打造智能家居. 小编已经收到魅族的邀请函,黑色简洁的盒子,就好像对开的大门,中间以中国结做装饰.里面的内容也是中国传统的窗花,窗花上的图案预示着发布会的内容.大概可以猜出有智能穿戴设备 智能家居 手机以及支付宝. 至于魅族会真正发布什么产品呢?请关注1.28日本站带来的第一时间报道,共同见证魅族智能生态圈.
  • 我只是讨厌屈服——柴静 我只是讨厌屈服——柴静 十年前,当陈虻问我如果做新闻关心什么时,我说关心新闻中的人--这一句话,把我推到今天. "人"常常被有意无意忽略,被无知和偏见遮蔽.这些思维,就埋在无意识之下.无意识是如此之深,以至于常常看不见他人,对自己也熟视无睹. 你和我是平等的 郝劲松剃着一个阿甘式的头,后脑勺剃光了,头发茬子硬硬地拱出来. 2006年3月21日上午10:03,北京市第一中级人民法院.他坐在原告的位子上开口说话:"审判长,通知我的开庭时间是10点,被告迟到,我是否能得到合理解释?" 审判长看他
  • 爱街开启场景O2O 引领移动互联网新发展 爱街开启场景O2O 引领移动互联网新发展 近年来,基于移动互联的O2O产品如雨后春笋般发展,乃至推动了传统行业"互联网+"的转型升级,然而权威数据显示,仅2015年上半年O2O夭折企业已达近百家,部分O2O企业已陷入发展瓶颈.对此,分析人士表示,这是市场"物竞天择"的必然结果,但同时也暴露出大家对O2O认识的不足. 的确,O2O是要实现线上线下的无缝连接,但并非通过技术打通线上线下这么简单,事实上其连接的真正核心是"场景",即在消费者需要的时候提供他们所需要的信息和服务.而这才是O2O的
  • 佳能1200D画幅是什么 佳能1200D画幅是什么 佳能1200D画幅是APS-C画幅相机.