第20章字符串中查找子串位置（暴力匹配）

课程目录第20章字符串中查找子串位置（暴力匹配）

第20章：字符串中查找子串位置（暴力匹配）：BF算法实现

各位同学，今天我们来聊聊字符串查找中最基础、最直观的算法——BF算法。

BF算法，全称是Brute-Force，翻译过来就是「暴力匹配」。别被「暴力」这俩字吓到，它其实是最朴素的思路：拿着子串，在主串里一个一个位置去试。说白了，就是最笨的办法，但也是最容易理解的办法。

20.1 什么是BF算法？

假设你有一个主串S，比如"hello world"，你想知道子串T"world"在不在里面，在的话在哪个位置。

BF算法的做法很简单：

从主串的第一个字符开始，和子串的第一个字符比较
如果相等，继续比较下一个字符
如果不相等，主串回退到第二个字符，子串回退到开头，重新比较
一直重复，直到找到匹配或者主串遍历完

我刚开始学C语言的时候，第一次接触字符串匹配，老师问我们怎么实现。我当时的想法就是：两个循环嵌套，外层遍历主串，内层遍历子串。嗯，这就是BF算法的核心思想。

20.2 BF算法的代码实现

直接上代码。我个人习惯把函数命名为str_index_bf，清晰明了。

#include <stdio.h>
#include <string.h>

/**
 * BF算法：在字符串S中查找子串T第一次出现的位置
 * @param S 主串
 * @param T 子串
 * @param pos 从主串的哪个位置开始查找（从0开始）
 * @return 成功返回子串起始下标，失败返回-1
 */
int str_index_bf(const char *S, const char *T, int pos) {
    int i = pos;   // 主串当前比较位置
    int j = 0;     // 子串当前比较位置
    int s_len = strlen(S);
    int t_len = strlen(T);

    // 边界检查
    if (pos < 0 || pos >= s_len) {
        return -1;
    }
    if (t_len == 0) {
        return 0;  // 空串约定返回0
    }

    while (i < s_len && j < t_len) {
        if (S[i] == T[j]) {
            // 字符相等，继续往后比较
            i++;
            j++;
        } else {
            // 字符不相等，主串回溯，子串重置
            i = i - j + 1;
            j = 0;
        }
    }

    // 判断是否匹配成功
    if (j == t_len) {
        return i - j;  // 返回子串起始位置
    } else {
        return -1;
    }
}

int main() {
    char S[] = "hello world, this is a test";
    char T[] = "world";

    int index = str_index_bf(S, T, 0);
    if (index != -1) {
        printf("子串 \"%s\" 在主串中的位置是：%d\n", T, index);
    } else {
        printf("未找到子串 \"%s\"\n", T);
    }

    return 0;
}

核心逻辑解析：

关键就在那个i = i - j + 1。当匹配失败时，主串指针i要回退到本轮匹配开始位置的下一个字符。而i - j正好是本次匹配的起始位置，再加1就是下一个位置。

20.3 图解BF算法执行过程

光说理论不够直观，我画了一张流程图，帮你理解BF算法的执行过程。

从流程图可以看出，BF算法的核心就是一个循环嵌套。外层循环控制主串的遍历，内层循环控制子串的比较。匹配成功就继续，匹配失败就回溯。

20.4 时间复杂度分析

情况	时间复杂度	说明
最好情况	O(n + m)	第一次比较就匹配成功，或者每次第一个字符就不匹配
最坏情况	O(n × m)	每次匹配到子串最后一个字符才失败，比如主串"aaaaa...b"，子串"aaa...b"
平均情况	O(n + m)	实际应用中，字符分布比较随机，平均性能还不错

其中n是主串长度，m是子串长度。

⚠️ 避坑指南：

我曾经在一个日志分析工具里用了BF算法，日志文件有几百兆，子串长度也不短。结果跑一次要好几秒，用户直接投诉了。后来才发现，日志里大量重复字符，触发了最坏情况。所以，如果你的数据有大量重复模式，BF算法要慎用。

20.5 BF算法的优缺点

优点：

实现简单，代码量少，容易理解
不需要预处理，直接开干
在大多数实际场景下，性能可以接受

缺点：

最坏情况时间复杂度高，O(n×m)
没有利用已经匹配过的信息，每次失败都要从头开始
对于大规模文本处理，效率偏低

20.6 实际项目中的经验

我记得有一次做嵌入式开发，要在单片机里实现一个简单的命令解析器。用户输入命令字符串，程序要匹配预定义的命令列表。那时候内存紧张，不能引入复杂的算法库。我就用BF算法手写了一个匹配函数。

为什么选BF？因为命令都很短，最长不超过20个字符，而且命令列表也就几十条。BF算法在这种场景下完全够用，而且代码简单，不容易出bug。

💡 我的建议：

BF算法适合以下场景：

子串长度较短（比如小于100个字符）
主串和子串的字符分布比较随机
对性能要求不高，或者数据量不大
需要快速实现，不想引入复杂算法

如果数据量大，或者有大量重复字符，建议用KMP、BM等更高效的算法。

20.7 代码优化小技巧

虽然BF算法简单，但也有一些优化空间。我分享几个小技巧：

提前计算长度：在循环外调用strlen，避免每次循环都计算。
边界剪枝：主串剩余长度小于子串长度时，直接返回-1。
使用指针：在性能敏感的场合，可以用指针操作代替数组下标。

来看一个优化版的代码：

int str_index_bf_opt(const char *S, const char *T, int pos) {
    int s_len = strlen(S);
    int t_len = strlen(T);

    if (pos < 0 || pos >= s_len || t_len == 0) {
        return (t_len == 0) ? 0 : -1;
    }

    // 边界剪枝：主串剩余长度不够，直接返回
    if (s_len - pos < t_len) {
        return -1;
    }

    int i, j;
    for (i = pos; i <= s_len - t_len; i++) {
        for (j = 0; j < t_len; j++) {
            if (S[i + j] != T[j]) {
                break;
            }
        }
        if (j == t_len) {
            return i;
        }
    }
    return -1;
}

这个版本用了两层for循环，逻辑更清晰。外层循环只遍历到s_len - t_len，避免了不必要的比较。

20.8 总结

BF算法是字符串匹配的入门算法，它简单、直观、容易实现。虽然效率不是最高的，但它是理解更高级算法的基础。你想想看，KMP算法就是在BF的基础上，加入了「部分匹配表」来避免回溯。没有BF，你怎么理解KMP为什么要那样优化？

我个人建议，初学者一定要亲手写一遍BF算法。不要复制粘贴，一个字一个字敲出来。调试过程中遇到的各种问题——比如数组越界、死循环、返回值错误——都是宝贵的经验。

好了，BF算法就讲到这里。代码不多，但值得你反复琢磨。下一章我们会讲KMP算法，到时候你会感谢今天认真学BF的自己。

公众号：蓝海资料掘金营，微信deep3321

📚 课程目录