BruteForce算法

今天参加了人工智能课程的选拔，大概130人选60个人，考察了BF算法和MaxHeap。

很遗憾两个都没写出来，回来后认真学习了一下BF算法，发现其实很简单。只是自己没学过算法。

什么是BruteForce算法？

BruteForce（暴力匹配）算法是一种最基础的字符串匹配算法。它的核心思想是：从主串的每一个位置开始，尝试与模式串进行逐字符比较，直到找到匹配或者遍历完主串。

时间复杂度：O(n*m)，其中n为主串长度，m为模式串长度。

代码实现

下面是C++实现，包含详细注释：

#include <iostream>
#include <string>
using namespace std;

// BruteForce字符串匹配算法
int bruteForce(const string& str, const string& pattern) {
    int n = str.length();      // 主串长度
    int m = pattern.length();  // 模式串长度

    for (int i = 0; i <= n - m; ++i) { // 从主串的每个位置尝试匹配
        int j = 0;
        while (j < m && str[i + j] == pattern[j]) {
            j++; // 逐字符比较
        }
        if (j == m) {
            return i; // 匹配成功，返回起始下标
        }
    }
    return -1; // 匹配失败
}

int main() {
    cout << "请输入主串:" << endl;
    string str;
    cin >> str;
    cout << "请输入模式串:" << endl;
    string pattern;
    cin >> pattern;
    int result = bruteForce(str, pattern);
    if (result != -1) {
        cout << "匹配成功，起始下标为: " << result << endl;
    } else {
        cout << "未找到匹配。" << endl;
    }
    return 0;
}

参考资料

• 字符串匹配算法详解

学习笔记, 算法 — 2025年6月17日