字符串中查找子串_cstring查找子字符串

字符串中查找子串_cstring查找子字符串子串查询首先,我们来定义两个概念,主串和模式串。我们在字符串A中查找字符串B,则A就是主串,B就是模式串。我们把主串的长度记为n,模式串长度记为m。由于是在主串中查找模式串,因此,主串的长度肯定比模式串长,n>m。因此,字符串匹配算法的时间复杂度就是n和m的函数。假设要从主串s=“goodgoogle”中找到t=“google”子串。根据我们的思考逻辑,则有:首先,我们从主串s第1位开始,判断s的第1个字符是否与t的第1个字.

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

  1. 子串查询
    首先,我们来定义两个概念,主串和模式串。我们在字符串 A 中查找字符串 B,则 A 就是主串,B 就是模式串。我们把主串的长度记为 n,模式串长度记为 m。由于是在主串中查找模式串,因此,主串的长度肯定比模式串长,n>m。因此,字符串匹配算法的时间复杂度就是 n 和 m 的函数。

假设要从主串 s = “goodgoogle” 中找到 t = “google” 子串。根据我们的思考逻辑,则有:

  • 首先,我们从主串 s 第 1 位开始,判断 s 的第 1 个字符是否与 t 的第 1 个字符相等。

  • 如果不相等,则继续判断主串的第 2 个字符是否与 t 的第1 个字符相等。直到在 s 中找到与 t 第一个字符相等的字符时,然后开始判断它之后的字符是否仍然与 t 的后续字符相等。

  • 如果持续相等直到 t 的最后一个字符,则匹配成功。

  • 如果发现一个不等的字符,则重新回到前面的步骤中,查找 s 中是否有字符与 t 的第一个字符相等。

  • 如下图所示,s 的第1 个字符和 t 的第 1 个字符相等,则开始匹配后续。直到发现前三个字母都匹配成功,但 s 的第 4 个字母匹配失败,则回到主串继续寻找和 t 的第一个字符相等的字符。

  • 如下图所示,这时我们发现主串 s 第 5 位开始相等,并且随后的 6 个字母全匹配成功,则找到结果。
    在这里插入图片描述
    这种匹配算法需要从主串中找到跟模式串的第 1 个字符相等的位置,然后再去匹配后续字符是否与模式串相等。显然,从实现的角度来看,需要两层的循环。第一层循环,去查找第一个字符相等的位置,第二层循环基于此去匹配后续字符是否相等。因此,这种匹配算法的时间复杂度为 O(nm)。其代码如下:

public void s1() {

    String s = "goodgoogle";

    String t = "google";

    int isfind = 0;



    for (int i = 0; i < s.length() - t.length() + 1; i++) {

        if (s.charAt(i) == t.charAt(0)) {

            int jc = 0;

            for (int j = 0; j < t.length(); j++) {

                if (s.charAt(i + j) != t.charAt(j)) {

                    break;

                }

                jc = j;

            }

            if (jc == t.length() - 1) {

                isfind = 1;

            }

        }

    }

    System.out.println(isfind);

}

  1. 字符串匹配
    字符串匹配算法的案例
    最后我们给出一道面试中常见的高频题目,这也是对字符串匹配算法进行拓展,从而衍生出的问题,即查找出两个字符串的最大公共字串。

假设有且仅有 1 个最大公共子串。比如,输入 a = “13452439”, b = “123456”。由于字符串 “345” 同时在 a 和 b 中出现,且是同时出现在 a 和 b 中的最长子串。因此输出 “345”。

对于这个问题其实可以用动态规划的方法来解决,关于动态规划,我们会在后续的课程会讲到,所以在这里我们沿用前面的匹配算法。

假设字符串 a 的长度为 n,字符串 b 的长度为 m,可见时间复杂度是 n 和 m 的函数。

  • 首先,你需要对于字符串 a 和 b 找到第一个共同出现的字符,这跟前面讲到的匹配算法在主串中查找第一个模式串字符一样。

  • 然后,一旦找到了第一个匹配的字符之后,就可以同时在 a 和 b 中继续匹配它后续的字符是否相等。这样 a 和 b 中每个互相匹配的字串都会被访问一遍。全局还要维护一个最长子串及其长度的变量,就可以完成了。

从代码结构来看,第一步需要两层的循环去查找共同出现的字符,这就是 O(nm)。一旦找到了共同出现的字符之后,还需要再继续查找共同出现的字符串,这也就是又嵌套了一层循环。可见最终的时间复杂度是 O(nmm),即 O(nm²)。代码如下:

public void s2() {

    String a = "123456";

    String b = "13452439";

    String maxSubStr = "";

    int max_len = 0;

		

    for (int i = 0; i < a.length(); i++) {

        for (int j = 0; j < b.length(); j++){

            if (a.charAt(i) == b.charAt(j)){

                for (int m=i, n=j; m<a.length()&&n<b.length(); m++,n++) {

                    if (a.charAt(m) != b.charAt(n)){

                    break;

                    }

                    if (max_len < m-i+1){

                        max_len = m-i+1;

                        maxSubStr = a.substring(i, m+1);

                    }

                }

            }

        }	

    }

    System.out.println(maxSubStr);

}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/171724.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 【开发工具】【smartctl】硬盘检测工具(smartctl)的使用

    【开发工具】【smartctl】硬盘检测工具(smartctl)的使用概述随着硬盘容量、速度的快速发展,硬盘的可靠性问题越来越重要,今天的单块硬盘存储容量可轻松达到1TB,硬盘损坏带来的影响非常巨大。不同的文件系统(xfs,reiserfs,ext3)都有自己的检测和修复工具。检测之前可以先使用dmesg命令查看有没有硬件I/O故障的日志,如果有,先用fsck看看是不是文件系统有问题,如果不是则可以使用下面介绍硬盘检测和优化方法来修复它。grep“error”/va/log/messages*;SMART是一种磁盘自我分析检测技术,早在90年代末就基本得到了

  • CentOS7关闭selinux[通俗易懂]

    1、为什么要关闭selinux初学者配置linux服务器时不成功,却没有头绪,那是因为在linux操作系统中默认开启了防火墙,SELinux也处于启动状态,一般状态为enforing。致使很多服务端口默认是关闭的。所以好多服务初学者明明配置文件正确,等验证时有时连ping也ping不通。建议初学者在未学到SELlinux与iptables之前,配置服务器把这两项都关掉。2、查看selinux状…

  • 关于数据存储类型的一点分析

    关于数据存储类型的一点分析

    2021年11月27日
  • JS跳转代码_js中跳转页面路径

    JS跳转代码_js中跳转页面路径一、常规的JS页面跳转代码1、在原来的窗体中直接跳转用2、在新窗体中打开页面用:3、JS页面跳转参数的注解参数解释:第2种:第3种:第4种:第5种:三、页面停留指定时间再跳转(如3秒)四、根据访客来源跳转的JS代码1、JS判断来路代码此段代码主要用于百度谷歌点击进入跳转,直接打开网站不跳转:2、JS直接跳转代码3、ASP跳转代码判断来路<%  ifinstr(Request.ServerVariables(“http_referer”),“www

  • to program_I Just Want To

    to program_I Just Want To在http://forum.doom9.org/showthread.php?t=109747上看到的一篇文章,讲得不错,翻译一下,以作备忘。原文是:InX264therearetwodeblockingparameters,calledDeblockingstrengthandDeblockingthreshold.Thestrengthp

  • 实时示波器_示波器proteus怎么找

    实时示波器_示波器proteus怎么找原创:转载请著名出处。代码整理后将在GIThub发出。本文主要介绍驱动以及连接问题。首先,如果我们要使用NI-VISA协议,我们必须安装VISA的驱动。我们可以先检查一下有没有。C:\Windows\System32或者C:\Windows\SysWOW64如果有,恭喜你,你省去一大笔时间。如果没有,恭喜你,这里将告诉你如何安装。https://dl…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号