算法 BF算法

　

bf算法

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

算法思想：

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

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

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

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

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

难理解之处：

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

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

②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;
}

运行程序：

相关阅读

BF算法详解

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

【计算广告】在线分配算法之 —— HWM（High water mark

该算法是雅虎工程师提出的一个解决合约制广告或者说GD（担保式投放）投放系统在线分配问题的贪心算法，思路很直接，下面是本人对照其论文

回归算法和决策树

一、回归算法 1.回归分析的概念 回归分析（regression analysis)是确定两种或两种以上变量间相互依赖的定量关系的一种统计分析

图的最短路径之迪杰斯特拉算法和弗洛伊德算法

文章目录一、迪杰斯特拉(Dijkstra)算法1、定义描述2、算法思想3、算法步骤4、算法图解二、弗洛伊德（Floyd）算法1、定义描述2、算法

游戏中AOI视野算法

AOI(Area Of Interest)，中文就是感兴趣区域。通俗一点说，感兴趣区域就是玩家在场景实时看到的区域；也就是AOI会随着英雄的移动改变而