bf算法字符串匹配c++

BF算法（Brute-Force）又称朴素匹配算法，是一种字符串匹配算法，其基本思想是将目标串中的每个字符与模式串中的每个字符逐个比较，如果都相等，则继续比较下一个字符，否则就将目标串中的指针移动到下一个位置，重新从目标串的该位置开始与模式串进行比较。

在C++中实现BF算法的代码如下：

int BF(string s, string p) {
    int s_len = s.length();
    int p_len = p.length();
    for (int i = 0; i <= s_len - p_len; i++) {
        int j = 0;
        for (; j < p_len; j++) {
            if (s[i+j] != p[j]) break;
        }
        if (j == p_len) return i;
    }
    return -1;
}

其中`s`为目标串，`p`为模式串。该算法的时间复杂度为$O(mn)$，其中$m$为目标串长度，$n$为模式串长度。

相关问题

bf字符串匹配算法c++

BF字符串匹配算法（Brute Force）是一种简单的模式匹配算法，也称为朴素匹配算法。它的思想是从主串的第一个字符开始，依次与模式串的每个字符进行比较，如果匹配成功，则继续比较下一个字符，否则主串的指针后移一位，重新从主串的下一个字符开始与模式串进行匹配。这个过程一直持续到主串的末尾或者匹配成功为止。

以下是BF字符串匹配算法的C++代码实现：

#include <iostream>
#include <string>

using namespace std;

int BF(string s, string p) {
    int i = 0, j = 0;
    while (i < s.length() && j < p.length()) {
        if (s[i] == p[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j == p.length()) {
        return i - j;
    } else {
        return -1;
    }
}

int main() {
    string s = "hello world";
    string p = "world";
    int pos = BF(s, p);
    if (pos != -1) {
        cout << "匹配成功，位置为：" << pos << endl;
    } else {
        cout << "匹配失败" << endl;
    }
    return 0;
}

C++用BF算法进行字符串匹配

在C++中，BF（Boyer-Moore Hunt）算法是一种高效的字符串搜索算法，用于查找主串中是否存在给定的模式串。BF算法的基本思想是从模式串的末尾开始，逐字符向右移动，如果当前字符匹配，则继续；如果不匹配，它会利用已知信息跳过大量的比较。

以下是BF算法的核心步骤：

1. **Bad Character Rule**（坏字符规则）：对于每个模式字符m[i]，找到其在主串s中最后的位置索引p，如果s[p] == m[i]，则可以尽可能地从这个位置向右移动，直到遇到第一个不匹配的字符，这时主串移动的距离等于该字符在模式串中的索引加一。

2. **Good Suffix Rule**（好后缀规则）：基于已知的信息，即使某个字符不匹配，也可以通过比较模式串的好后缀和剩余部分来确定移动距离。例如，如果模式串的后缀与前面剩余的部分匹配，那么就可以直接跳到下一个未匹配的位置。

C++实现BF算法通常需要预先计算模式串的一些辅助数据，如坏字符表和好后缀表。这里不是一个完整的代码示例，但基本框架如下：

void BM_search(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    if (m > n)
        return;

    // 坏字符表和好后缀表的初始化...
    vector<int> badChar(m), goodSuffix(m);

    int i = m - 1;
    while (i < n) {
        // 检查是否匹配
        bool match = true;
        for (int j = 0; j < m && match; ++j) {
            if (text[i - j] != pattern[m - j - 1])
                match = false;
        }

        // 如果匹配，更新当前位置
        if (match)
            i -= m;

        // 根据坏字符和好后缀规则调整位置
        else {
            int dist = INT_MAX;
            if (i < m - 1)
                dist = min(dist, badChar[text[i]]);
            if (dist != INT_MAX)
                i += dist;
            else {
                // 如果badChar表无效，退化为简单遍历
                for (; i < n && text[i] != pattern[0]; ++i);
            }
        }
    }
}