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

全栈程序员-站长 • 2022年8月21日下午1:00 • 未分类 • 阅读 9

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}