揭秘BF算法：字符串匹配的暴力美学

一、先解答 Day7 思考题问循环队列为什么要牺牲一个位置答为了区分队空和队满队空front rear队满(rear 1) % MAX front如果不牺牲一个位置队空和队满的判断条件会一样程序无法区分。二、今天学习目标理解什么是字符串模式匹配掌握BF 算法暴力匹配 / 朴素匹配完整可运行代码 图文思路时间复杂度分析三、什么是字符串模式匹配给定主串abcabcd模式串abcd问题模式串在主串中第一次出现的位置在哪里如果找到返回起始下标没找到返回 -1。这就是字符串匹配是搜索引擎、编辑器、病毒查杀的基础。四、BF 暴力匹配思路最简单、最直观的思路用主串第i个字符和模式串第j个字符对比相等i、j继续比下一个不相等回溯i 回到本轮起始位置的下一个j 回到 0直到j走完模式串 → 匹配成功五、BF 算法完整代码C 语言可直接运行#include stdio.h #include string.h // BF字符串匹配算法 // str主串pattern模式串找到返回起始下标失败返回-1 int BF_Match(char str[], char pattern[]) { int len_str strlen(str); int len_pat strlen(pattern); int i 0; // 主串指针 int j 0; // 模式串指针 while (i len_str j len_pat) { if (str[i] pattern[j]) { // 字符相等继续往后 i; j; } else { // 不相等回溯 i i - j 1; j 0; } } // 匹配成功j走完了模式串 if (j len_pat) { return i - j; } return -1; } // 主函数测试 int main() { char str[] abcabcd; char pattern[] abcd; int pos BF_Match(str, pattern); if (pos ! -1) { printf(匹配成功起始位置%d\n, pos); } else { printf(未找到匹配\n); } return 0; }运行结果匹配成功起始位置3六、算法分析最好情况一次就匹配成功时间复杂度O(n m)最坏情况每次都对比到最后一个才不匹配时间复杂度O(n × m)缺点效率低大量重复比较优点逻辑最简单最容易理解和手写七、今日小练习可直接交作业题目主串ababcabcac模式串abcac使用上面 BF 代码求匹配位置。测试代码int main() { char str[] ababcabcac; char pattern[] abcac; int pos BF_Match(str, pattern); printf(pos %d\n, pos); return 0; }结果pos 5八、思考题Day9 解答BF 算法效率很低有什么办法可以减少回溯让匹配更快九、明日预告Day9KMP 算法入门解决 BF 重复比较的问题实现无回溯高效字符串匹配面试高频难点。