文档章节

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

 毛朱
发布于 2015/08/27 20:13
字数 303
阅读 104
收藏 4

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、最长公共子串 其实这是一个序贯决...

大数据之路
2013/03/25
0
2
JavaScript 算法与数据结构 - javascript-algorithms

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

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

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

qcer
2017/12/20
0
0
JavaScript 算法与数据结构

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

a独家记忆
06/08
0
0
动态规划之两个字符串的最大子序列

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

u011068702
03/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

golang使用protobuf简易教程

参考文档:https://blog.csdn.net/qq_15437667/article/details/78425151 一、安装protobuf # 去github.com/golang/protobuf下载源码包,# 拷贝到 $GOPATH/src/github.com/golang/protobuf......

科陆李明
28分钟前
0
0
8月16日 上课截图

小丑鱼00
43分钟前
0
0
Nginx负载均衡、配置SSL

Nginx负载均衡 在 /usr/local/nginx/conf/vhost/ 下创建一个文件,写入以下内容 加载后用curl测试可以访问设置的网站 www.qq.com ssl原理 HTTPS是一种加密的http协议,如果HTTP通信的数据包在...

黄昏残影
47分钟前
0
0
String 源码阅读笔记

String源码阅读 本人学习笔记,内容来自于阅读源码和其他博客,水平有限,如有错误,烦请指正。 详情参考: Java 7 源码学习系列(一)——String 请别再拿“String s = new String("xyz");...

等到烟火清凉_
48分钟前
4
0
Coding and Paper Letter(十二)

资源整理。<!-- more --> 1 Coding: 1.R语言生成的ppt,GeoStat2018会议报告,时空模式分析的报告。 geostat18 2.欧空局哨兵和SMOS的工具集,关于对地观测数据的处理与分析的docker容器。 ...

胖胖雕
49分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部