首页    技术博客    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;
}
不知道是否有更好的算法,我一直在找寻.
推荐阅读
  • go

    深入理解C++中的KMP算法：高效字符串匹配的利器

    深入理解C++中的KMP算法：高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法，探讨其在字符串匹配问题上的优势。通过对比暴力匹配（BF）算法，展示KMP算法如何利用前缀表优化匹配过程，显著提升效率。 ... [详细]
  • io

    Python 异步编程：深入理解 asyncio 库（上）

    Python 异步编程：深入理解 asyncio 库（上）
    本文介绍了 Python 3.4 版本引入的标准库 asyncio，该库为异步 IO 提供了强大的支持。我们将探讨为什么需要 asyncio，以及它如何简化并发编程的复杂性，并详细介绍其核心概念和使用方法。 ... [详细]
  • char

    深入理解KMP算法中的next数组：北大OJ 2406题解

    本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • go

    优化ListView性能

    优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能，包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • go

    技术分享：从动态网站提取站点密钥的解决方案

    技术分享：从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥，特别是针对验证码（reCAPTCHA）的处理方法。通过结合Selenium和requests库，提供了详细的代码示例和优化建议。 ... [详细]
  • object

    新浪笔试题

    1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • char

    USACO 2014 Jan - Moolympics区间记录优化算法

    题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]
  • char

    Java面试题解析

    本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • io

    深入理解Python的os和sys模块

    本文详细解析了Python中的os和sys模块，介绍了它们的功能、常用方法及其在实际编程中的应用。 ... [详细]
  • range

    寻找满足特定条件的整数N的最大和(a+b)

    本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]
  • include

    C++实现经典排序算法

    C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出，帮助读者全面了解这些排序方法的特点。 ... [详细]
  • go

    使用动态规划算法求解0-1背包问题

    本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现，详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]
  • command

    深入理解设计模式与七大原则

    本文详细探讨了Java中的24种设计模式及其应用，并介绍了七大面向对象设计原则。通过创建型、结构型和行为型模式的分类，帮助开发者更好地理解和应用这些模式，提升代码质量和可维护性。 ... [详细]
  • io

    Java并发编程：LinkedBlockingQueue的实际应用

    本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]
  • char

    C语言实现小写金额转换为大写金额

    在金融和会计领域，准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据，还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法，确保数据的标准化和规范化。 ... [详细]
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社区 版权所有