算法 BF算法

逃离我推掉我的手 2022-05-27 12:15 272阅读 0赞

BF算法是字符匹配的一种算法，也称暴力匹配算法

算法思想：

从主串s1的pos位置出发，与子串s2第一位进行匹配

若相等，接着匹配后一位字符

若不相等，则返回到s1前一次匹配位置的后一位，接着与s2的起始位进行匹配

直到与s2全部匹配成功，则返回在s1中开始完全匹配的下标

简单说这个算法的思想就是匹配失败，就重新从上一次匹配位置的下一位开始匹配

难理解之处：

①i = i - j + 2，这一步是若匹配失败，从上一次匹配位置的下一位开始

i - j是去掉前面匹配过的次数，+ 2是到达下一个匹配位置

![20180418172541368][]

②i - s2.length()，它返回的是第一次匹配成功时在s1中的下标

也就是去掉与s2匹配的个数，就是下标

代码：

#include <iostream>
    #include <string>
    using namespace std;
    //BF算法（暴力匹配算法）
    int BF(string s1, string s2, int pos)
    {
        int i = pos - 1;
        int j = 0;
        while(i < s1.length() && j < s2.length()) //若i和j都大于字符串的长度就结束循环
        {
            if(s1[i] == s2[j])
            {
                i++;
                j++;
            }
            else
            {
                i = i - j + 2;
                j = 1;
            }
        }
        if(j >= s2.length())
            return i - s2.length(); //返回的是第一次匹配到的字符的下标
        return 0;
    }
    int main()
    {
        string s1 = "abcdabcdefg";
        string s2 = "abcde";
        int pos;
        cin >> pos; //输入s1开始匹配的位置
        cout << BF(s1, s2, pos);
        return 0;
    }

运行程序：

![70][]

[20180418172541368]: /images/20220527/bb5c6623bc414754b167474037858f45.png
[70]: /images/20220527/61cd414f27aa4a7597508e9f4eca5a7a.png

发表评论取消回复

表情：

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

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

相关阅读

相关字符串BF算法和KMP算法

什么是串数据结构中，字符串要单独用一种存储结构来存储，称为串存储结构。这里的串指的就是字符串。字符串通常是由零个或多个字符组成的有限序列。一般地，由n个字符串构成的

冷不防/ 2023年10月03日 14:06/ 0 赞/ 32 阅读

相关算法：字符串匹配算法：BF算法、RK算法

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

系统管理员/ 2023年07月10日 08:42/ 0 赞/ 62 阅读

相关 BF算法与KMP算法

BF算法与KMP算法都是用来查找主串中子串的位置，也就是模式匹配。 BF算法的简单粗暴，缺点是每趟匹配不成功时，存在大量回溯，导致程序效率低下，而KMP算法充分利用了成功匹

墨蓝/ 2023年02月28日 12:48/ 0 赞/ 132 阅读

相关 LeetCode题解 - BFS算法

BFS算法文章目录 BFS算法一、算法框架二、LeetCode题目详解 111. 二叉树的最小深度（简单）

- 日理万妓/ 2023年01月19日 10:59/ 0 赞/ 11 阅读

相关算法 DFS与BFS

一、DFS（深度优先搜索） > DFS: 深度优先遍历DFS与树的先序遍历比较类似。假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点然后依次访问它

傷城~/ 2022年12月20日 03:27/ 0 赞/ 185 阅读

相关字符串：BF算法

BF算法介绍 BF算法，即暴风(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续

爱被打了一巴掌/ 2022年06月01日 11:46/ 0 赞/ 196 阅读

相关算法 BF算法

BF算法是字符匹配的一种算法，也称暴力匹配算法算法思想：从主串s1的pos位置出发，与子串s2第一位进行匹配若相等，接着匹配后一位字符若不相等，则返回到s

逃离我推掉我的手/ 2022年05月27日 12:15/ 0 赞/ 273 阅读

相关 BFS，dijkstra算法

http://ac.jobdu.com/problem.php?pid=1008 题目描述：给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，

雨点打透心脏的1/2处/ 2022年05月25日 11:11/ 0 赞/ 216 阅读

相关 BF算法详解

BF算法 BF（Brute Force)算法也就是传说中的“笨办法”，是一个暴力/蛮力算法。设串S和P的长度分别为m,n，则它在最坏情况下的时间复杂度是O(m\

淩亂°似流年/ 2022年03月19日 05:17/ 0 赞/ 325 阅读

相关 BF算法和KMP算法详解

串匹配问题给定两个字符串S和T，在主串S中查找子串T的过程称之为串匹配（模式匹配）,T称之为模式。这样一类的问题在实践中应用非常广泛。在文本处理系统、操作系统、编译系统、数

灰太狼/ 2022年02月22日 15:24/ 0 赞/ 262 阅读