串的模式匹配算法-BF（Brute-Force）算法

拼搏现实的明天。 2022-05-24 04:29 182阅读 0赞

## Bruce-Force算法 ##

### 1.思路： ###

简单暴力的一个算法，如果遇到字符不匹配，**主串i指针回溯到本次匹配位置的下一个位置**，而**模式串则重新回到0（开始的位置）**，开始下一轮的匹配。

成功匹配的条件自然事**模式串指针j走到头**，也就是**j=length-1**，length为模式串长度。**跳出循环表示为j=length**

### 2.算法复杂度 ###

**O（n\*m）**，n，m分别是两个串长度。

### 3.小吐一番 ###

有兴趣的小火半可以看下同时写的**KMP算法** ：[点击打开链接][Link 1]

只能说这个更为简单易懂但就是容易Running Time Error....，有了BF的基础再去看上面的KMP哦~：）友好提示

## Bruce-Force算法实现 ##

#include<iostream>
    #include<string>
    using namespace std;
    
    int Brute_Force_Algorithm(string Primer_Str, string Str)
    {
    	int i = 0, j = 0;
    	int Length1 = Primer_Str.length();
    	int Length2 = Str.length();
    	while (i < Length1&&j < Length2)
    	{
    		if (Primer_Str[i] == Str[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i = i - j + 1;   //字符不匹配，则主串的i指针回溯到本次开始的位置的下一个位置
    			j = 0;    //模式串指针回到串头
    		}
    	}
    	if (j == Length2)
    		return i - Length2 + 1;
    	else
    		return -1;
    }
    
    int main()
    {
    	string Primer_Str, Str;
    	cin >> Primer_Str >> Str;
    	cout << Brute_Force_Algorithm(Primer_Str, Str) << endl;
    	return 0;
    }

BY\_THE\_WAY: Sad，隔了半个月才出了两篇，渣男在努力~，下周高数over进入B（it)树啦

[Link 1]: https://blog.csdn.net/szu_crayon/article/details/80385210

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关串-KMP模式匹配算法

5.7 KMP 模式匹配算法你们可以忍受朴素模式匹配算法的低效吗?也许不可以、也许无所谓。但在很多年前我们的科学家们，觉得像这种有多个0和1重复字符的字符串，却需要挨个

「爱情、让人受尽委屈。」/ 2022年09月30日 03:50/ 0 赞/ 209 阅读

相关串-定义和模式匹配算法

5.2 串的定义今天我们就是来研究"串"这样的数据结构。先来看定义。串( string )是由零个或多个字符组成的有限序列，又名叫字符串。一般记为s= "a1

╰半橙微兮°/ 2022年09月28日 13:27/ 0 赞/ 160 阅读

相关串的模式匹配-BF算法

串的模式匹配经常需要用到，判断一个字符串是否是另外一个字符串的一部分。前者称为子串或模式，后者成为主串或正文串。先用最简单的BF算法实现串的模式匹配。算法思路：先从主串

妖狐艹你老母/ 2022年09月28日 13:09/ 0 赞/ 199 阅读

相关串的模式匹配（BF算法，KMP算法）

模式匹配(Pattern Matching) 即子串定位运算（Index函数）。算法目的：确定主串中所含子串第一次出现的位置（定位） ——即如何实现 Index(S,T,p

约定不等于承诺〃/ 2022年08月22日 04:00/ 0 赞/ 205 阅读

相关串的模式匹配算法-KMP

include<iostream> include<cstdio> include<cstring> using namespace std;

r囧r小猫/ 2022年06月06日 14:12/ 0 赞/ 181 阅读

相关串的模式匹配算法-BF（Brute-Force）算法

Bruce-Force算法 1.思路：简单暴力的一个算法，如果遇到字符不匹配，主串i指针回溯到本次匹配位置的下一个位置，而模式串则重新回到0（开始的位置），开始下

拼搏现实的明天。/ 2022年05月24日 04:29/ 0 赞/ 183 阅读

相关串的模式匹配算法-KMP算法

KMP算法 1.开挂传送门：[点击打开链接][Link 1] 这个算法理解起来有点难受，建议看下简单的串模式匹配算法 BF算法刷下经验，如上链接。 2.优化匹

深藏阁楼爱情的钟/ 2022年05月24日 04:27/ 0 赞/ 249 阅读

相关串的匹配模式算法

关于算法原理，网上有很多优秀的博客都有讲解，这里我就只记录一下自己用代码实现的过程 BF算法（c）： 1.主串与模式串逐个字符进行比较， 2.出现字符

系统管理员/ 2022年05月15日 13:47/ 0 赞/ 199 阅读

相关串的模式匹配-KMP算法

include<stdio.h> include<string.h> typedef struct String { char base[50

阳光穿透心脏的1/2处/ 2022年05月08日 12:16/ 0 赞/ 193 阅读

相关串的模式匹配算法：KMP算法

串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，在主串s中找到等于子串t的过程称为模式匹配，如果找到，则称匹配成功，函数返回t在s中的首次出现的存储位置(

深藏阁楼爱情的钟/ 2022年04月24日 10:58/ 0 赞/ 244 阅读