首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

求公共子串问题以及其改进算法

作者：茶茶 | 来源：互联网 | 2023-05-17 17:18
求公共子串问题以及其改进算法问题的提出：设计一个算法，求两个字符串s1,s2的最长公共子字符串的长度．例如字符串"shaohui","huishao"的
求公共子串问题以及其改进算法 问题的提出：     设计一个算法，求两个字符串s1,s2的最长公共子字符串的长度．例如字符串"shaohui","huishao"的最长公共子字符串为"shao",因此，结果为4.     最早看到这个问题，大约是２年前在CSDN程序员杂志的编程擂台上面，后来又在程序员考试的题目当中遇到，但是他们所使用的方法都需要消耗比较多的时间，这里我先简单说明一下这个问题的原始的解答方法，然后再介绍我的改进算法． 　 1.以前的算法 算法思想：对于两个字符串s1,s2(假设字符串s1长度大于字符串s2的长度),设的长度为m,那么s2的子串可以按照其长度分成m类 假设s1="shaohui",s2="ahui"，则s2的子串可以分成以下几类 4:ahui 3:ahu,hui 2:ah,hu,ui 1:a,h,u,i 然后按照长度从大到小去匹配s1,如果某个子串也是s1的子串，则找到问题的答案了． 这是我用C写的例子程序，可以作为参考      1    #include <iostream>     2    #include <cstring>      3    using namespace std;      4    /*     5    * Get the length of common substring of s1 and s2     6    * if there is no common substring between s1 and s2, return 0     7    */     8    int commstr(char *s1, char *s2)     9    {    10           char *src,*dst;    11           int len,len1,len2,cnt,srcidx,dstidx,srcbeg,dstbeg;    12               13           len1 = strlen(s1);    14           len2 = strlen(s2);    15           //assure that the length of src is large then dest    16           if (len1 > len2)    17           {    18                  src = s2;    19                  dst = s1;    20                  len = len1;    21                  len1 = len2;    22                  len2 = len;    23           }    24           else    25           {    26                  src = s1;    27                  dst = s2;    28           }    29               30           len = len1;    31           while (len > 0)    32           {    33                  for (srcidx=0; srcidx+len<=len1; srcidx++)    34                  {    35                         for (dstidx=0; dstidx+len<=len2; dstidx++)    36                         {    37                                for (cnt=0; cnt    38                                       if (src[srcidx+cnt] != dst[dstidx+cnt])    39                                              break;    40                                if (cnt >= len)//common string is found    41                                       goto found;    42                         }    43                  }    44                  len --;    45           }                                      46           found: return len;    47    }     48    int main(int argc, char **argv)    49    {    50           if (argc >= 3)    51                  cout<<commstr(argv[1],argv[2]);    52               53           return 0;    54    }
说明：13-29行是保证字符串s1的长度大于字符串s2的长度，如果strlen(s1) 关于这方面的更多的解答请参考程序员杂志的编程擂台，或者1998年的程序员考试的下午试题第一题． 　 时间复杂度分析:     假设s1的长度为n,s2的长度为m,　按照最坏的打算，假设不能够找到公共子串（也就是公共子串的长度为0) 进行的比较次数为(也就是第38行代码的执行次数) 为了便于计算我们假设n=m 利用高中的数列求和的知识,很容易得到,则原时间复杂度为O(n4) 　 2.我的改进算法     原来的求解方法的时间复杂度为O(n4),实际上还有比较大的改进余地,原来的问题完全可以在O(n*m)的时间内得到求解.     仔细分析原来的求解的过程，对于子串s2的任意一个长度k,字符串s1和s2中的任意两个字符之间都要进行一次比较,而当k减少1的时候,s1和s2中的任意两个字符又要进行比较一次,这显然是冗余的.故如果利用以前的比较结果,时间复杂度可以降低到O(n3).     下面具体说说我的改进算法     将字符串s1和s2分别写在两把直尺上面(我依然用s1,s2来表示这两把直尺),然后将s1固定,s2的尾部和s1的头部对齐,然后逐渐移动直尺s2,比较重叠部分的字符串中的公共子串的长度,直到直尺s2移动到s1的尾部.在这个过程中求得的最大长度就是s1,s2最大子串的长度. 下图是求解过程的图示,蓝色部分表示重叠的字符串,红色的部分表示重叠部分相同的子串 其中s1="shaohui",s2="ahui",最后的求得的结果为3            按照这个思想，很容易得到这个例子程序      1    #include <iostream>     2    #include <string.h>      3    using namespace std;      4    int commstr(char *s1, char *s2)     5    {     6           int len1 = strlen(s1),len2 = strlen(s2),len = len1 + len2;     7           int cnt,s1start,s2start,idx,max = 0,curmax;     8                9           for (cnt=0; cnt    10           {    11                  s1start = s2start = 0;    12                  if (cnt     13                         s1start = len1 - cnt;    14                  else    15                         s2start = cnt - len1;    16                      17                  curmax = 0;    18                  for (idx=0; (s1start+idx    19                  {    20                         if (s1[s1start+idx] == s2[s2start+idx])    21                                curmax++;    22                         else    23                         {    24                                max = curmax > max ? curmax : max;    25                                curmax = 0;    26                         }    27                  }    28                  max = curmax > max ? curmax : max;     29           }    30               31           return max;    32    }      33    int main(int argc, char **argv)    34    {    35           if (argc <3)    36                  return 0;    37           printf("%s/t%s:%d",argv[1],argv[2],commstr(argv[1],argv[2]));    38           return 0;    39    }
时间复杂度分析: 容易计算,时间复杂度O(n,m)=(n+m)m 令n=m 则时间复杂度O(n)=n2,与以前的算法相比较,降低了2次,应该算是比较大的改进了  　 3.递归的方法     我用Python写了一个递归的求解方法，如下 def commstr(long,short) :
    if short in long :   
        return len(short)
    return max(commstr(long,short[:-1]),commstr(long,short[1:]))

print commstr('shaohui','huishao') 
    代码很简单，原理也很简单，尽管是使用的递归，但是基本思想还是以前的求解方法：对于字符串a,b,尽量用b的最大的子字符串c去匹配另外一个字符串a，如果c不是a的子串，那么用字符串b的长度比b少1的子串去匹配a,直到匹配到了为止或者子串的长度为0．         为了便于参考，我也用C写了个，不用解释了，因为注释已经很清楚了 #include
#include

#define BUFFER_SIZE 255

int commstr(char *s1, char *s2)
{
    char buf[BUFFER_SIZE];
    int start,cnt=-1,len1=strlen(s1),len2=strlen(s2);

    for (start=0; start+len2    {
        for (cnt=0; cnt            if (s1[start+cnt] != s2[cnt])
                break;
            if (cnt >= len2)//如果在s1中找到一个字串和s1相同
                break;
    }

    if (cnt >= len2)//如果s2是s1的子串
        return len2;

    //把s2中后len2-1个字符构成的串同s1比较,并求字串长度
    len1 = commstr(s1,s2+1);

    //把s2中前len2-1个字符构成的串同s1比较,并求字串长度
    strncpy(buf,s2,len2-1);
    buf[len2-1] = '/0';
    len2 = commstr(s1,buf);
    //返回较大者
    return len1 > len2 ? len1 : len2;
}

int main(int arc, char *argv)
{
    printf("%d",commstr("shaohui","huishao"));
    return 0;
}
不知道是否有更好的算法,我一直在找寻.
推荐阅读
  • get

    Codeforces Round #566 (Div. 2) A~F个人题解

    Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]
  • get

    CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

    本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]
  • netty

    PHP Eloquent ORM 中的关联查询扩展

    本文探讨了如何在 PHP 的 Eloquent ORM 中实现数据表之间的关联查询，并通过具体示例详细解释了如何将关联数据嵌入到查询结果中。这不仅提高了数据查询的效率，还简化了代码逻辑。 ... [详细]
  • netty

    毕业设计：基于机器学习与深度学习的垃圾邮件（短信）分类算法实现

    毕业设计：基于机器学习与深度学习的垃圾邮件（短信）分类算法实现
    本文详细介绍了如何使用机器学习和深度学习技术对垃圾邮件和短信进行分类。内容涵盖从数据集介绍、预处理、特征提取到模型训练与评估的完整流程，并提供了具体的代码示例和实验结果。 ... [详细]
  • netty

    rm: cannot remove `/usr/local/tmp/‘: Directory not empty

    ###问题删除目录时遇到错误提示：rm:cannotremoveusrlocaltmp’:Directorynotempty即使用rm-rf，还是会出现 ... [详细]
  • netty

    2016年10月25日数学考试：斐波那契数列与矩阵快速幂的应用

    本次考试于2016年10月25日上午7:50至11:15举行，主要涉及数学专题，特别是斐波那契数列的性质及其在编程中的应用。本文将详细解析考试中的题目，并提供解题思路和代码实现。 ... [详细]
  • netty

    解决C++编译错误C3867的方法

    解决C++编译错误C3867的方法
    本文详细介绍了在不同版本的Visual Studio中，如何正确处理成员函数指针以避免编译错误C3867。同时，提供了一个具体的代码示例及其优化方案。 ... [详细]
  • netty

    使用Pandas高效读取SQL脚本中的数据

    使用Pandas高效读取SQL脚本中的数据
    本文详细介绍了如何利用Pandas直接读取和解析SQL脚本，提供了一种高效的数据处理方法。该方法适用于各种数据库导出的SQL脚本，并且能够显著提升数据导入的速度和效率。 ... [详细]
  • datetime

    深入解析 Django ORM：Model 和 Field 类型

    本文详细探讨了 Django 的 ORM（对象关系映射）机制，重点介绍了其如何通过 Python 元类技术实现数据库表与 Python 类的映射。此外，文章还分析了 Django 中各种字段类型的继承结构及其与数据库数据类型的对应关系。 ... [详细]
  • datetime

    图论问题解析：POJ2762 从u到v或从v到u的可达性判断（强连通分量缩点与单向连通性检测）

    本文深入探讨了POJ2762问题，旨在通过强连通分量缩点和单向连通性的判断方法，解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤，并附带完整的代码示例。 ... [详细]
  • web

    HTTP请求与响应机制详解

    本文深入探讨了HTTP请求和响应对象的使用，详细介绍了如何通过响应对象向客户端发送数据、处理中文乱码问题以及常见的HTTP状态码。此外，还涵盖了文件下载、请求重定向、请求转发等高级功能。 ... [详细]
  • web

    UnityGUI 扩展与自定义控件

    本文介绍了如何通过扩展 UnityGUI 创建自定义和复合控件，以满足特定的用户界面需求。内容涵盖简单和静态复合控件的实现，并展示了如何创建复杂的 RGB 滑块。 ... [详细]
  • version

    选择适合生产环境的Docker存储驱动

    选择适合生产环境的Docker存储驱动
    本文旨在探讨如何在生产环境中选择合适的Docker存储驱动，并详细介绍不同Linux发行版下的配置方法。通过参考官方文档和兼容性矩阵，提供实用的操作指南。 ... [详细]
  • web

    深入解析网络存储技术

    本文详细介绍了网络存储技术的基本概念、分类及应用场景。通过分析直连式存储（DAS）、网络附加存储（NAS）和存储区域网络（SAN）的特点，帮助读者理解不同存储方式的优势与局限性。 ... [详细]
  • web

    实现页面自动加载更多内容功能：类微博和Pinterest的设计

    在现代Web应用中，当用户滚动到页面底部时，自动加载更多内容的功能变得越来越普遍。这种无刷新加载技术不仅提升了用户体验，还优化了页面性能。本文将探讨如何实现这一功能，并介绍一些实际应用案例。 ... [详细]
author-avatar
茶茶
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有