[算法系列之十二]字符串匹配之蛮力匹配

[算法系列之十二]字符串匹配之蛮力匹配引言字符串匹配是数据库开发和文字处理软件的关键。幸运的是所有现代编程语言和字符串库函数,帮助我们的日常工作。不过理解他们的原理还是比较重要的。字符串算法主要可以分为几类。字符串匹配就是其中之一。当我们提到字符串匹配算法,最基本的方法就是所谓的蛮力解法,这意味着我们需要检查每一个文本串中的字符是否和匹配串相匹配。一般来说我们有文本串和一个匹配串(通常匹配串短于文本串)。我们需要做的就是回答这个匹配串是

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

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

引言

字符串匹配是数据库开发和文字处理软件的关键。幸运的是所有现代编程语言和字符串库函数,帮助我们的日常工作。不过理解他们的原理还是比较重要的。

字符串算法主要可以分为几类。字符串匹配就是其中之一。当我们提到字符串匹配算法,最基本的方法就是所谓的蛮力解法,这意味着我们需要检查每一个文本串中的字符是否和匹配串相匹配。一般来说我们有文本串和一个匹配串(通常匹配串短于文本串)。我们需要做的就是回答这个匹配串是否出现在文本串中。

概述

字符串蛮力匹配法的原理非常简单。我们必须检查匹配串的第一个字符与文本串的第一个字符是否相匹配,就如下图片所述。

这里写图片描述
我们通过比较文本串的和匹配串的第一个字符来开始

如果他们不匹配我们移向文本串的第二个字符。现在我们比较匹配串的第一个字符和文本串第二个字符。如果他们不匹配我们继续向前移动,直到我们遇到一个相匹配的或直到我们到达文本串的最后。

这里写图片描述
因为文本串第一个字符和匹配串的第一个字符不匹配,我们向前移动到文本串的的第二个字符。现在我们比较文本串的第二个字符和匹配串的第一个字符!

假设第一个字符匹配,我们移向匹配串的第二个字符去和文本串的下一个字符比较。如下面图片所示。

这里写图片描述
如果文本串的一个字符和匹配串的第一个字符相匹配,我们向前移动到匹配串第二个字符和文本串的下一个字符做匹配

如果仅仅是因为匹配串的第一个字符与文本串的某个字符相匹配,那并不意味着这个匹配串出现在文本串中,也仅仅是第一个字符出现在文本串中,其他说明不了。我们必须向前移动匹配串,看看完整的匹配串是否包含在文本文本串中。

这里写图片描述
匹配串相匹配

代码

/*-------------------------------- * 日期:2015-02-05 * 作者:SJF0115 * 题目: 字符串匹配之蛮力匹配 * 博客: ------------------------------------*/
#include <iostream>
using namespace std;


int SubString(string text,string pattern){
    int m = text.size();
    int n = pattern.size();
    // 蛮力匹配
    for(int i = 0;i < m - n;++i){
        int j = 0;
        while(j < n && text[i+j] == pattern[j]){
            ++j;
        }//while
        // match
        if(j == n){
            return i;
        }//if
    }//for
    return -1;
}

int main(){
    string text("hello world!");
    string pattern("o wo");
    int result = SubString(text,pattern);
    cout<<"下标位置->"<<result<<endl;
    return 0;
}

复杂度

就像我说的这个算法是缓慢的。实际上每一个算法,只要在它的名字中包含“蛮力”二字,这个算法都是很缓慢的,其时间复杂度是O(n*m)。这里m是文本串的长度,而n是匹配串的长度。

原文连接

Computer Algorithms: Brute Force String Matching

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

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

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

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

(0)


相关推荐

  • FileProvider的权限路径

    FileProvider的权限路径

  • matlab for循环语句实例_matlab如何循环

    matlab for循环语句实例_matlab如何循环MATLABfor循环MATLAB中for循环是一个重复的控制结构,可以有效地写一个循环,只是执行的次数是特定的。MATLABfor循环语法:MATLAB中的for循环的语法如下:forindex=values…endfor循环的值有下述三种形式之一:格式 描述 initval:endval 将索引变量从初始到终值递增1,并重复执行程序语句,直到索引值大于终值。 initval:step:endval

  • 网页音乐播放器代码

    网页音乐播放器代码网页音乐播放器代码如果你也想往自己的博客里,网页里加入音乐播放器,只要复制下面的网页音乐播放器代码,做适当的修改就可以啦!有很多播放器可以选择,不要挑花眼哦!中true或1表示自动播放,false或0表示手动播放loop=”true”中的true或1表示重复播放,f

  • 屡次停止运行怎么解决_很抱歉已停止运行解决方法

    屡次停止运行怎么解决_很抱歉已停止运行解决方法背景我一般运行appium都是在osx或者linux上面,最近在教几个同事使用appium做些自动化(爬虫)的事,有几个人使用的是windows,配置环境搞了很久,服务跑起来了之后,用代码运行,又报了上面标题的错误。问题分析首先判断,这是一个python的错误,也就是说,不是appium本身的问题,那就从两点开始分析,要么是系统环境问题,要么是哪里的配置问题。先从配置的问题开始下手,毕竟新手一般都容易犯一些低级错误。但是拿着同事的代码在另一位同事的机器(osx)上跑,怎么都

  • SSM整合,非常详细的SSM整合[通俗易懂]

    SSM整合,非常详细的SSM整合[通俗易懂]对于ssm框架网上有很多,这里只是自己为大家提供的一个ssm整合框架参考分享,这个前提是基于maven的管理工具写的,如果觉得写得不好,博主这边已经把代码上传了:不妨可以参考代码再理解学习:https://download.csdn.net/download/qq_30764991/11012764如果觉得文章不错,对你有帮助,请作者喝杯咖啡,谢谢!如果对您有帮助,请多多支持.多少都…

  • LeetCode1两数之和

    LeetCode1两数之和题目:给定一个整数数列,找出其中和为特定值的那两个数。你可以假设每个输入都只会有一种答案,同样的元素不能被重用。示例:给定nums=[2,7,11,15],target=9因为nums[0]+nums[1]=2+7=9所以返回[0,1]分析:可以直接遍历两遍数组,第一遍用target-nums[i],第二遍找nums数组中是否存在target-num…

发表回复

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

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