博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LCS_最大公共子串查找算法解析
阅读量:5877 次
发布时间:2019-06-19

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

hot3.png

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

网上有篇是用一个一维数组(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;  

}  

转载于:https://my.oschina.net/u/347386/blog/498344

你可能感兴趣的文章
CSS魔法堂:Transition就这么好玩
查看>>
【OpenStack】network相关知识学习
查看>>
centos 7下独立的python 2.7环境安装
查看>>
[日常] 算法-单链表的创建
查看>>
前端工程化系列[01]-Bower包管理工具的使用
查看>>
使用 maven 自动将源码打包并发布
查看>>
Spark:求出分组内的TopN
查看>>
Python爬取豆瓣《复仇者联盟3》评论并生成乖萌的格鲁特
查看>>
关于跨DB增量(增、改)同步两张表的数据小技巧
查看>>
飞秋无法显示局域网好友
查看>>
学员会诊之03:你那惨不忍睹的三层架构
查看>>
vue-04-组件
查看>>
Golang协程与通道整理
查看>>
解决win7远程桌面连接时发生身份验证错误的方法
查看>>
C/C++ 多线程机制
查看>>
js - object.assign 以及浅、深拷贝
查看>>
python mysql Connect Pool mysql连接池 (201
查看>>
Boost在vs2010下的配置
查看>>
android camera(四):camera 驱动 GT2005
查看>>
一起谈.NET技术,ASP.NET伪静态的实现及伪静态的意义
查看>>