BP 算法

【概述】

暴力（Brute Force，BF）算法，是最简单的一种模式匹配算法，没有预处理阶段

其本质是暴力枚举，通过一个大小为 $1$ 的滑动窗口，循环来检查从 $n-m+1$ 到 $m$ 的范围中是否存在满足条件 T[s+i]=P[i] 的有效位移 $s$

在最坏的情况下，BF 算法会进行 $n-m+1$ 轮匹配，每轮匹配都会进行 $m$ 次匹配，由于在一般的应用场景中 $n>>m$，因此 BF 算法的最坏时间复杂度为：

$$O((n-m+1)*m)=O(nm)$$

【基本思想】

BF 算法的基本思想如下：

1）用两个计数指针 i、j 指示文本串 T 和模式串 P 中当前正待比较的字符位置

2）从文本串 T 的第一个字符开始，与模式串 P 的第一个字符开始比较

• 若相等：继续逐个比较两者的后续字符
• 若不等：终止本轮匹配，令文本串 T 的指针 i 从上一开始的匹配点后移一位，令模式串 P 的指针 j 归零，重新开始一轮匹配

3）待匹配完毕后，若模式串 P 中的每一字符依次与 T 中的一个连续子串序列相等，则匹配成功

【实现】

int BF(char *T, char *P) { //BF算法
    int tLen = strlen(T);  //文本串长度
    int pLen = strlen(P);  //模式串长度
    int i = 0;             //文本串的当前位置
    int j = 0;             //模式串的当前位置

    while (i < tLen && j < pLen) {
        if (i > tLen - pLen + 1)
            break;
        if (T[i] == P[j]) { //T的第i个与P的第j个字符相等时
            i++;
            j++;
        } else {            //T的第i个与P的第j个字符不等时
            i = i - j + 1;  //i从上一开始的匹配点后移一位
            j = 0;
        }
    }

    if (j == pLen)    //模式串位置与模式串长度相同说明匹配成功
        return i - j; //返回匹配位置
    return -1;        //匹配失败
}