文档章节

LCS_最大公共子串查找算法解析

 毛朱
发布于 2015/08/27 20:13
字数 303
阅读 103
收藏 4
点赞 0
评论 0

http://blog.csdn.net/hairetz/article/details/4664846



最大公共子串算法可用动态规划来解。

网上有篇是用一个一维数组(string,本质是一维)来记录匹配信息。效果还能让人满意,贴出代码与个人理解。

  

string lcs_search(string str1, string str2)  

{  

    if (str1.length() < str2.length())                   //保证str1为母串(较长的哪个串)  

    {  

        string strTemp = str1;  

        str1 = str2;  

        str2 = strTemp;  

    }  

      

    int * sign = new int[str1.length()];          //sign里存储的是母串(str1)每个元素前向能与子串匹配的公共子串数  

    //比如sign[12]==5;则说明从str1[12]往前5个元素(包括[12]),能与str2的某一段匹配  

    int length = 0;  

    int end = 0;  

    for (int i = 0; i < str2.length(); i++)  

    {  

        for (int j = str1.length() - 1; j >= 0; j-- )  

        {  

              

            if (str2[i] == str1[j])  

            {  

                if (i == 0 || j == 0)                          //i==0,则母串的j元素必然只能匹配一个,j==0同理  

                    sign[j] = 1;            

                else                                           //由于该次j匹配,所以子串可以+1  

                    sign[j] = sign[j - 1] + 1;  

            }  

            else                                               //不匹配,则此位置的sign归零  

                sign[j] = 0;  

            if (sign[j] > length)                             //结果存储  

            {  

                length = sign[j];  

                end = j;  

            }  

        }  

    }  

    delete []sign;  

    return str1.substr(end - length + 1, length);  

}  

  

  

  

int main()  

{    

    string a="123456789abcdefghijklmn2131.dfdfdf",b="123456sdkk123456789abcddkfdfkd123456789abcde";  

    string c;  

    c=lcs_search(a,b);  

    cout<<c<<endl;   

    return 0;  

}  


© 著作权归作者所有

共有 人打赏支持
粉丝 19
博文 147
码字总数 170387
作品 0
济南
动态规划算法之:最长公共子序列 & 最长公共子串(LCS)

1、先科普下最长公共子序列 & 最长公共子串的区别: 找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。 2、最长公共子串 其实这是一个序贯决...

xrzs ⋅ 2013/03/25 ⋅ 2

JavaScript 算法与数据结构 - javascript-algorithms

javascript-algorithms 包含了多种基于 JavaScript 的算法与数据结构。 每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 数据结构 数据结构是在计算机中...

匿名 ⋅ 05/31 ⋅ 0

Algo-Practice: 算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

记录一些算法实践 目录 Java篇 一、基础算法 七种基础排序 二叉堆 K选取问题 链表判环问题 N皇后问题 两指针扫描算法举例 位运算(求首个bit1,求bit1的个数,寻找奇数项) 最小栈的实现 横纵有...

qcer ⋅ 2017/12/20 ⋅ 0

动态规划之两个字符串的最大子序列

1、问题 求两个字符串的最大子序列 1)、子序列和子字符串有区别,子字符串(子串)必须连续,列如 s1 = "ABCDAB" s2= "BBCDAAB" s1和s2最大子序列有"BCDA","BCDB", "CDAB","ABAB","BCAB".....

u011068702 ⋅ 03/24 ⋅ 0

有趣的算法问题之巧思妙想

有趣的算法 算法之所以有趣,在于他能够化繁为简,他能概括统御世间万物,将一个复杂的问题归结为一个非常简单的问题。其实所有高阶的算法,都可以用两个大的方法去解决,而且屡试不爽。分别...

Nicholas_Jela ⋅ 2017/09/06 ⋅ 0

两个字符串的最长连续公共子串

LCS(Longest Common Subsequence) 就是求两个字符串最长公共子串的问题。引入: LCS(Longest Common Subsequence) 就是求两个字符串最长公共子串的问题。 比如: String str1 = new String("...

ranjiewen ⋅ 2016/09/20 ⋅ 0

动态规划

动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长非降子序列(LIS) 最大乘积子串 Unique Paths Unique Paths II Minimum Path Sum Triangle 最...

廖少少 ⋅ 2017/09/27 ⋅ 0

使用搜索技术实现 URL 智能匹配

所谓URL智能匹配,简单来说,就是要在内存中实现一个微型的搜索引擎。为了便于说明,假设需要识别的只有以下这5个网站,网站名称对应搜索引擎中的术语是“文档”,每个文档都有其对应的ID、文...

xrzs ⋅ 2013/01/12 ⋅ 0

【算法系列 四】 String

字符串循环左移(九度OJ1362),要求时间复杂度O(N),空间复杂度O(1) 这是一道基本的题目,简单说来就是三次翻转 比如:abcdef 左移两位 cdefab 过程: ab 翻转 ba cdef 翻转 fedc 将上面两个翻...

Hosee ⋅ 2016/04/18 ⋅ 0

求所有最大公共子序列的算法实现

最近看了很多关于LCS(Longest common subsequence problem,最长公共子序列)的文章,大部分问题都只是求出最大公共子序列的长度,或者打印处其中的任意一个最大子序列即可,但是如何快速的打印...

长平狐 ⋅ 2013/03/12 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

R计算IV

参考文章 #读取文件 rawdata = read.csv("/path/to/csv/file",header=T) colnames(rawdata)[18] <- "y" //重命名因变量y #数据分区 训练集测试集 trainIdx <- sample(nrow(rawdata), round(......

火力全開 ⋅ 6分钟前 ⋅ 0

SQL老司机,在SQL中计算 array & map & json数据

摘要: 场景 通常,我们处理数据,一列数据类型要么是字符串,要么是数字,这些都是primitive类型的数据。 场景 通常,我们处理数据,一列数据类型要么是字符串,要么是数字,这些都是primi...

阿里云云栖社区 ⋅ 6分钟前 ⋅ 0

SQL老司机,在SQL中计算 array & map & json数据

摘要: 场景 通常,我们处理数据,一列数据类型要么是字符串,要么是数字,这些都是primitive类型的数据。 场景 通常,我们处理数据,一列数据类型要么是字符串,要么是数字,这些都是primi...

猫耳m ⋅ 17分钟前 ⋅ 0

关于ireport自定义变量类型为list的时候

自己摸石头过河,我真的应该去趟市中心图书馆,借本真正靠谱的教材 网上的东西,只有0.01%是有用的,还有0.99%是垃圾,剩下的99%是垃圾的复制品。。 哎!~ 问题是这样的,报表带sql,从db中获...

炑炑milina ⋅ 18分钟前 ⋅ 0

Spring mvc ContextLoaderListener 原理解析

对于熟悉Spring MVC功能,首先应从web.xml 开始,在web.xml 文件中我们需要配置一个监听器 ContextLoaderListener,如下。 <!-- 加载spring上下文信息,最主要的功能是解析applicationContex...

轨迹_ ⋅ 18分钟前 ⋅ 0

阿里云发布企业数字化及上云外包平台服务:阿里云众包平台

摘要: 阿里云正式发布旗下众包平台业务(网址:https://zhongbao.aliyun.com/),支持包括:网站定制开发,APP、电商系统等软件开发,商标、商品LOGO、VI、产品包装设计、营销推广、大数据人...

阿里云官方博客 ⋅ 20分钟前 ⋅ 0

Redis安装异常解决办法

官网地址:http://redis.io/ 官网下载地址:http://redis.io/download 1. 下载Redis源码(tar.gz),并上传到Linux 2. 解压缩包:tar zxvf redis-2.8.17.tar.gz 3. 进入解压缩后的文件夹:c...

slagga ⋅ 24分钟前 ⋅ 0

006. 深入JVM学习—年轻代

1. 年轻代图片 年轻代(Young)属于JVM堆内存空间的一个组成部分 所有使用关键字new新实例化的对象一定会在伊甸园区进行保存,而对于存活区保存的一定是已经在伊甸园区存在一段时间并且经过了...

影狼 ⋅ 25分钟前 ⋅ 0

如何成为一个合格的程序员

偶尔的,我会被人问道:如何成为一名优秀的程序员,更或者,如何成为一名程序员。每次人们问起,我都力图给出不同的答案。因此,我的答案是各种各样的。下面就是我认为的成为一名优秀的程序员...

柳猫 ⋅ 26分钟前 ⋅ 0

cups error_log日志暴增

日志内容 File \"/usr/lib/cups/notifier/dbus\" has insecure permissions 解决(未验证适用范围) sudo service cups stopsudo rm /etc/cups/subscriptions.conf*sudo rm -r /var/cac......

一介码夫_Hum ⋅ 30分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部