数据结构——BF算法 - 指南

BF算法

在字符串模式匹配中，BF算法是最直观的实现方式，也被称为朴素模式匹配算法。它的核心逻辑是“暴力遍历、逐个比较”，虽然效率不是最优，但因逻辑简单、易于理解，是字符串匹配的基础方法。

1. BF算法的根本思想

：就是BF算法的核心思路从主串的每一个可能的起始位置开始，依次与模式串的每个字符逐一比较。具体来说，假设主串为$S$（长度为$n$），模式串为$T$（长度为$m$），我们需从主串的第0个字符开始，尝试将$S$的子串$S[i..i+m-1]$与$T$进行匹配（$i$从0到$n-m$）；若某一次子串与$T$完全匹配，则返回起始位置$i$；若遍历完所有可能的$i$后仍未匹配，则返回-1表示失败。

2. BF算法的匹配过程

为了更清晰地理解匹配逻辑，我们通过“指针移动”来拆解过程：

• 定义两个指针$i$（主串指针，初始为0）和$j$（模式串指针，初始为0）；
• 比较$S[i]$和$T[j]$：
  • 若相等：$i$和$j$同时加1，继续比较下一个字符；
  • 若不相等：$i$回溯到“上一次起始位置的下一个位置”（即$i=i-j+1$），$j$重置为0，重新开始匹配；
• 重复上述步骤，直到$j=m$（模式串完全匹配，返回$i-m$作为起始位置）或$i>n-m$（主串遍历完，匹配失败）。

以“主串$S=$‘ababcabcacbab’，模式串$T=$‘abcac’”为例，匹配过程如下：

• 初始$i=0,j=0$：$S[0]{=}^{\prime }{a}^{\prime }$与$T[0]{=}^{\prime }{a}^{\prime }$相等，$i=1,j=1$；
• $S[1]{=}^{\prime }{b}^{\prime }$与$T[1]{=}^{\prime }{b}^{\prime }$相等，$i=2,j=2$；
• $S[2]{=}^{\prime }{a}^{\prime }$与$T[2]{=}^{\prime }{c}^{\prime }$不相等，$i=0-2+1=-1+1=0$？ 这里纠正，实际$i$初始是0，第一次不相等时，$i=0-2+1=-1$？ 不对，应该是$i$初始从0开始，第一次比较到$i=2,j=2$不相等，此时$i$回溯到$0+1=1$（由于上一次起始位置是0，回溯后起始位置是1），$j=0$；
• 重新比较$S[1]{=}^{\prime }{b}^{\prime }$与$T[0]{=}^{\prime }{a}^{\prime }$不相等，$i$回溯到2，$j=0$；
• 以此类推，直到找到匹配位置或遍历结束。

3. BF算法的代码实现

以下是BF算法的C语言实现，函数返回模式串在主串中首次出现的起始位置，失败则返回-1：

// BF算法：s为主串，t为模式串，n为主串长度，m为模式串长度
int BF(char s[], char t[], int n, int m) {
int i = 0, j = 0;
while (i < n && j < m) {
if (s[i] == t[j]) { // 字符相等，继续比较下一个
i++;
j++;
} else { // 字符不相等，主串指针回溯，模式串指针重置
i = i - j + 1;
j = 0;
}
}
if (j == m) return i - m; // 匹配成功，返回起始位置
else return -1; // 匹配失败
}

代码说明：

• 循环条件i < n && j < m：确保主串和模式串都未遍历完；
• 字符相等时，i和j同时后移；不相等时，i回到“上一次起始位置的下一个位置”，j重置为0，重新开始匹配；
• 若j == m，说明模式串已完全匹配，返回起始位置i - m；否则返回-1表示失败。

4. BF算法的性能分析

BF算法的时间复杂度与主串、模式串的匹配情况密切相关：

• 最好情况：模式串的第一个字符就与主串的当前起始字符不匹配。例如，主串是“abcdef”，模式串是“xyz”，每次只需比较1个字符就能确定不匹配，时间复杂度为$O(n+m)$（$n$为主串长度，$m$为模式串长度）。
• 最坏情况：每次比较都到模式串的最后一个字符才不匹配，且主串有大量重复字符。例如，主串是“aaaaaab”，模式串是“aaab”：
  • 第一次匹配：$i=0,j=0$到$j=3$时不匹配，$i$回溯到1，$j=0$；
  • 第二次匹配：$i=1,j=0$到$j=3$时不匹配，$i$回溯到2，$j=0$；
  • 以此类推，直到找到匹配或遍历完主串。此时时间复杂度为$O(n\times m)$，当$n$和$m$较大时，效率极低。

综上，BF算法的优势是逻辑方便、易于实现，适合模式串较短或匹配概率较低的场景；但在最坏情况下效率较差，这也为后续更高效的KMP算法提供了优化的动力。理解BF算法的“暴力回溯”逻辑，是掌握字符串模式匹配进阶算法的基础。