首页    技术博客    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

    Java String与StringBuffer的区别及其应用场景

    Java String与StringBuffer的区别及其应用场景
    本文主要介绍了Java中String和StringBuffer的区别，String是不可变的，而StringBuffer是可变的。StringBuffer在进行字符串处理时不生成新的对象，内存使用上要优于String类。因此，在需要频繁对字符串进行修改的情况下，使用StringBuffer更加适合。同时，文章还介绍了String和StringBuffer的应用场景。 ... [详细]
  • random

    sklearn数据集库中的常用数据集类型介绍

    sklearn数据集库中的常用数据集类型介绍
    本文介绍了sklearn数据集库中常用的数据集类型，包括玩具数据集和样本生成器。其中详细介绍了波士顿房价数据集，包含了波士顿506处房屋的13种不同特征以及房屋价格，适用于回归任务。 ... [详细]
  • random

    计算机存储系统的层次结构及其优势

    计算机存储系统的层次结构及其优势
    本文介绍了计算机存储系统的层次结构，包括高速缓存、主存储器和辅助存储器三个层次。通过分层存储数据可以提高程序的执行效率。计算机存储系统的层次结构将各种不同存储容量、存取速度和价格的存储器有机组合成整体，形成可寻址存储空间比主存储器空间大得多的存储整体。由于辅助存储器容量大、价格低，使得整体存储系统的平均价格降低。同时，高速缓存的存取速度可以和CPU的工作速度相匹配，进一步提高程序执行效率。 ... [详细]
  • random

    Python正则表达式学习记录及常用方法

    Python正则表达式学习记录及常用方法
    本文记录了学习Python正则表达式的过程，介绍了re模块的常用方法re.search，并解释了rawstring的作用。正则表达式是一种方便检查字符串匹配模式的工具，通过本文的学习可以掌握Python中使用正则表达式的基本方法。 ... [详细]
  • random

    自动轮播，反转播放的ViewPagerAdapter的使用方法和效果展示

    自动轮播，反转播放的ViewPagerAdapter的使用方法和效果展示
    本文介绍了如何使用自动轮播、反转播放的ViewPagerAdapter，并展示了其效果。该ViewPagerAdapter支持无限循环、触摸暂停、切换缩放等功能。同时提供了使用GIF.gif的示例和github地址。通过LoopFragmentPagerAdapter类的getActualCount、getActualItem和getActualPagerTitle方法可以实现自定义的循环效果和标题展示。 ... [详细]
  • random

    Java中闭包的争论以及闭包的定义和特性

    闭包一直是Java社区中争论不断的话题，很多语言都支持闭包这个语言特性，闭包定义了一个依赖于外部环境的自由变量的函数，这个函数能够访问外部环境的变量。本文以JavaScript的一个闭包为例，介绍了闭包的定义和特性。 ... [详细]
  • request

    javascript – 如何自动格式化文本框输入

    Birthdate ... [详细]
  • bit

    将字符串数字拆分成单个数字_【LeetCode】842. 将数组拆分成斐波那契序列

    将字符串数字拆分成单个数字_【LeetCode】842. 将数组拆分成斐波那契序列
    【LeetCode】842.SplitArrayintoFibonacciSequence将数组拆分成斐波那契序列(Medium)(JAVA)题目描述：Givenas ... [详细]
  • js

    @用法做回复

    实现时主要问题在于怎么将所有对象给找出来，替换成user.name的形式。Overridepublicvoidsave(Comme ... [详细]
  • js

    由CStringW(wchar_t)不能正常打印收集的

    由CStringW(wchar_t)不能正常打印收集的
    WIN7、VS2010（工程字符集为Unicode）：源代码如下：CStringWline;rs是ODBC取得的结果集（有汉字），调试发现line能成功读取line.Form ... [详细]
  • c语言

    第3章 感受（一）——3.1. Hello world 经典版

    第3章 感受（一）——3.1. Hello world 经典版
    [回到目录]白话C++第3章.感受Helloworld!,HelloC++，我们来了！3.1.Helloworld经典版毫无疑义，一 ... [详细]
  • random

    C#生成随机数的三种方法及其问题分析

    本文介绍了C#中生成随机数的三种方法，并分析了其中存在的问题。首先介绍了使用Random类生成随机数的默认方法，但在高并发情况下可能会出现重复的情况。接着通过循环生成了一系列随机数，进一步突显了这个问题。文章指出，随机数生成在任何编程语言中都是必备的功能，但Random类生成的随机数并不可靠。最后，提出了需要寻找其他可靠的随机数生成方法的建议。 ... [详细]
  • js

    [刷题] LeetCode 3 Longest Substring Without Repeating Character

    [刷题] LeetCode 3 Longest Substring Without Repeating Character
    要求在一个字符串中寻找没有重复字母的最长子串思路滑动窗口如果当前窗口没有重复字母，j右移，直到包含重复字母i右移，直到不包含重复字母用数组记录字母是否出现过，判断重复实现1clas ... [详细]
  • controller

    NET CORE读取Excel.xlsx单元格内的图片，并关联当前业务ID推送图片到指定服务器

    NETCORE读取Excel.xlsx单元格图片的场景xlsx转换xls，一般是批量导入业务数据，例如：药品的图片，医师资格证，商品上架、商家营业资质、水果信 ... [详细]
  • instance

    Java面向对象8常用类2（MathString）

    Java面向对象8常用类2（MathString）
    Math1、直接使用，无需导包packagejava.lang;2、final修饰类不能被继承publicfinalclassMath3、构造器私有化ÿ ... [详细]
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社区 版权所有