算法 BF算法-蒲公英云

算法 BF算法

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