字符串匹配——枚举法[通俗易懂]

字符串匹配——枚举法[通俗易懂]字符串匹配——枚举法给定主串T和模式串P,返回P在T中首次出现的位置,如果P不存在于T中,返回-1。这样的问题就是字符串匹配问题,这里先给出枚举法的思想。设主串T的长度为n,模式串P的长度为m。主串从0到n-m,每次选取连续的m个字符,跟模式串P的m个字符进行一一比较。伪代码BruteForce(T,P)01fors<-0ton-m02j<-003//check

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

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

字符串匹配——枚举法

给定主串T和模式串P,返回P在T中首次出现的位置,如果P不存在于T中,返回-1。

这样的问题就是字符串匹配问题,这里先给出枚举法的思想。

设主串T的长度为n,模式串P的长度为m。

主串从0到n-m,每次选取连续的m个字符,跟模式串P的m个字符进行一一比较。

伪代码

BruteForce(T, P)
01 for s <- 0 to n - m
02  j <- 0
03  // check if T[s...s+m-1] = p[0...m-1]
04  while T[s+j] = P[j] do
05      j <- j + 1
06      if j = m then return s;
07 return -1

实现代码

// 布鲁特逼近法也就是穷举法
int bruteForce(const string &T,const string &P) {
    // 主串的长度
    int n = T.length();
    // 模式串的长度
    int m = P.length();
    for(int i = 0; i <= n - m; i++) {
        // 比较串T[i...i+m-1]和P[0...m-1]
        for(int j = 0; j < m; j++) {
            // 匹配失败则T指向下一个元素
            // P从零开始
            if(T[i + j] != P[j]) {
                break;
            }
            // 在主串中找到模式串
            if(j == m - 1) {
                // 返回模式串在主串的最早出现位置
                return i;
            }
        }
    }
    // 未在主串中找到模式串
    return -1;
}

测试主程序

#include <iostream>
#include <string>

using namespace std;

// 布鲁特逼近法也就是穷举法
int bruteForce(const string &T,const string &P) {
    // 主串的长度
    int n = T.length();
    // 模式串的长度
    int m = P.length();
    for(int i = 0; i <= n - m; i++) {
        // 比较串T[i...i+m-1]和P[0...m-1]
        for(int j = 0; j < m; j++) {
            // 匹配失败则T指向下一个元素
            // P从零开始
            if(T[i + j] != P[j]) {
                break;
            }
            // 在主串中找到模式串
            if(j == m - 1) {
                // 返回模式串在主串的最早出现位置
                return i;
            }
        }
    }
    // 未在主串中找到模式串
    return -1;
}

/** IN at the thought of though OUT 7 **/
int main() {
    // 主串和模式串
    string T, P;
    while(true) {
        // 获取一行
        getline(cin, T);
        getline(cin, P);
        int res = bruteForce(T, P);
        if(res == -1) {
            cout << "主串和模式串不匹配。" << endl;
        } else {
            cout << "模式串在主串的位置为:" << res << endl;
        }
    }
    return 0;
}

算法分析

最坏情况

  • 外层循环:n-m
  • 内层循环:m
  • 总计(n-m)m = O(nm)

最好情况

  • n-m

完全随机的主串和模式串

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

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

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

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

(0)


相关推荐

  • 一键ghost备份不了的原因_ghost系统恢复

    一键ghost备份不了的原因_ghost系统恢复大家都有想要给重要的东西备份吧,系统也是可以备份还原的,小编这里给大家分享一键Ghost备份还原系统的方法,如果你有需要对系统进行备份或还原就可以用这个一键备份还原方法了。一键Ghost备份还原备份的系统镜像不仅可以在本机进行还原还可以在其他的电脑上还原操作系统,很多朋友需要对系统备份不知道怎么操作,小编接下来就给大家详细介绍操作方法。Ghost系统的备份:1、系统之家一键重装系统是一个非常受欢迎…

  • 模拟电子线路复习笔记( 六) —— 集成运算放大器原理及其运用「建议收藏」

    模拟电子线路复习笔记( 六) —— 集成运算放大器原理及其运用「建议收藏」模拟电子线路复习笔记(六)——集成运算放大器原理及其运用本文是对模电的第六章的集成运算放大器原理及其运用知识点的笔记总结。全文手写,附有例题解析,帮助加深理解。1.知识点总结2.习题解析…

  • VScode快捷键(最全)[通俗易懂]

    VScode快捷键(最全)[通俗易懂]按Press功能FunctionCtrl+Shift+P,F1显示命令面板ShowCommandPaletteCtrl+P快速打开QuickOpenCtrl+Shift+N新窗口/实例Newwindow/instanceCtrl+Shift+W关闭窗口/实例Closewindow/instance基础编辑Basicediting按Press功…

  • java对象转换map

    java对象转换map背景介绍原理说明反射概念功能作用实现方式方法介绍实例展示对象转MAP背景介绍  今天在项目研发的过程中遇到这样一个需求,在一个统一处理类的入口要将所有后面处理流程需要用到的值统一塞进上下文的MAP对象中,这其中就包括了一持久层的DO对象。  如果对于对象进行逐个遍历是可以实现这个需求,但代码量比较大,所以一直在寻求一种比较合理的处理方式。后来发现可以通过反射的方式实现这个功能。原理

  • gateway网关详解_天翼网关扩展wifi

    gateway网关详解_天翼网关扩展wifi文章目录Gateway简介网关的功能搭建Gateway网关路由断言工厂路由过滤器全局过滤器过滤器执行顺序跨域问题处理Gateway简介Gateway是SpringCloud中的网关组件,SpringCloudGateway旨在提供一种简单而有效的方式来路由到API。SpringCloud在1.x版本中都是使用Zuul网关,但在2.x版本中使用Gateway替代了Zuul。Zuul是基于Servlet的实现,属于阻塞式编程。而SpringCloudGateway则是基于Spring5中提供的We

    2022年10月11日
  • 在报关的过程中会不会出现两个商检

    在报关的过程中会不会出现两个商检问题:1、我刚接触报关,我想知道在报检后如果检验检疫局要商检,那么在接下来的报关过程中我们还会再要商检吗?2、还有我想知道法检是指哪些检验,三检和法检有什么区别,我知道三检包括商检那么法检报不包括呢?回答:1.只有报检手续都办好了,出具通关单后,凭通关单才可以报关。报关过程和商检已经没有关系了。报关中不存在两个商检。但是商检整个流程会分别在报关前后完成。所以,可能让你混淆以为是两个商检。

发表回复

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

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