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

字符串匹配——枚举法[通俗易懂]字符串匹配——枚举法给定主串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)


相关推荐

  • pytorch、pycharm与tensorflow[通俗易懂]

    pytorch、pycharm与tensorflow[通俗易懂]**pytorch**jupyter打开方式:打开AnacondaPrompt,输入activatepytorch,进而输入jupyternotebook。查看当前环境:condainfo–envs查看库:piplist或者condalist更新库:pipinstall–upgrade库名运行快捷键:shift+enter安装新的模块:condainstall模块名pipinstall名在jupyter中打开.py文件:在Home中新建.ipynb

  • bert原理详解(duhamel原理)

    一文读懂BERT(从原理到实践)2018年的10月11日,Google发布的论文《Pre-trainingofDeepBidirectionalTransformersforLanguageUnderstanding》,成功在11项NLP任务中取得stateoftheart的结果,赢得自然语言处理学界的一片赞誉之声。本文是对近期关于BERT论文、相关文章、代码进…

  • 在pycharm中配置Anaconda以及pip源配置

    在pycharm中配置Anaconda以及pip源配置在学习推荐系统、机器学习、数据挖掘时,python是非常强大的工具,也有很多很强大的模块,但是模块的安装却是一件令人头疼的事情。现在有个工具——anaconda,他已经帮我们集成好了很多工具了!anaconda里面集成了很多关于python科学计算的第三方库,主要是安装方便,而python是一个编译器,如果不使用anaconda,那么安装起来会比较痛苦,各个库之间的依赖性就很难连接的很好。在wind

  • 判断一个数是否为素数c#(判断一个数是否为素数的算法)

    C++判断一个数是否为素数算法C++判断一个数是否为素数算法完整源码(定义,实现,main函数测试)C++判断一个数是否为素数算法完整源码(定义,实现,main函数测试)#include<cassert>#include<iostream>template<typenameT>boolis_prime(Tnum){boolresult=true;if(num<=1){return0;

  • win10更改pip源方法

    win10更改pip源方法win10更改pip源win10安装TensorFlow卡崩具体做法win10安装TensorFlow卡崩更改为国内清华大学镜像源,即可。具体做法在c:\user(或者用户)\电脑的用户名\,目录下创建一个命名为“pip”的文件夹(如:C:\Users\Administrator\pip),在该文件夹下创建一个命名为“pip.ini”的文件,在该文件中写入以下内容:[global]in…

  • PHP的几个常用加密函数

    PHP的几个常用加密函数

    2021年10月12日

发表回复

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

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