BF

Concept

BF 算法，即暴力(Brute Force)算法，是普通的 模式匹配 算法，BF 算法的思想就是将目标串 S 的第一个字符与模式串 T 的第一个字符进行匹配，若相等，则继续比较 S 的第二个字符和 T 的第二个字符；若不相等，则比较 S 的第二个字符和 T 的第一个字符，依次比较下去，直到得出最后的匹配结果。（百度百科）

例如，对于目标串 S("ababcabcacbab")和模式串 T("abcac")，那么其匹配过程如下：

(1) 首先，将模式串 T 与目标串 S 的首字符对齐，逐个判断相对应的字符是否相等，如下图所示：

(2) 上图中，由于模式串 T 和目标串 S 的第 3 个字符匹配失败，所以此时将模式串 T 后移一个字符的位置，采用同样的方法重新进行匹配，如下图所示：

(3) 上图中可以看到，两个串依旧匹配失败，模式串 T 继续后移一个位置，如下图所示：

(4) 上图依然匹配失败，模式串 T 继续向后移动，直到移动到下图所示的位置才匹配成功：

GIF演示:

可以看到，假设目标串 S 的长度为 n，模式串 T 的长度为 m，那么遍历目标串的时间复杂度为 $O(n)$，而遍历子串的长度为 $O(m)$，所以 BF 算法的时间复杂度就是 $O(n)∗O(m)=O(nm)$

Code

// Brute Force算法实现字符串匹配
int bruteForce(string text, string pattern) {
    int n = text.length();
    int m = pattern.length();

    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }
        if (j == m) {
            return i; // 返回匹配的位置
        }
    }
    
    return -1; // 没有找到匹配的子串
}

完整代码

#include <iostream>
#include <string> // C++ string类

using namespace std;

// Brute Force算法实现字符串匹配
int bruteForce(string text, string pattern) {
    int n = text.length();
    int m = pattern.length();

    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }
        if (j == m) {
            return i; // 返回匹配的位置
        }
    }
    
    return -1; // 没有找到匹配的子串
}

int main() {
    string text = "Hello, World!";
    string pattern = "World";
    
    int result = bruteForce(text, pattern);
    
    if (result != -1) {
        cout << "Pattern found at index " << result << endl;
    } else {
        cout << "Pattern not found" << endl;
    }

    return 0;
}

优点:

1. 思路简单直观,编程实现相对容易。

2. 一定可以找到最优解(如果存在的话)。

3. 适用于规模较小的问题。

缺点:

1. 时间复杂度通常很高,随着问题规模的增大,计算量呈指数级增长。

2. 空间复杂度也可能较高,需要存储所有可能的解。

3. 对于大规模问题,计算量往往超出计算机能力。