BF

BF（Brute Force）

在一个字符串中查找另一个字符串的操作称为模式匹配。其中，被查找的字符串被称为文本串，需要查找的子串称为模式串。

查找子串的最简单的算法就是采用暴力匹配的方式。暴力匹配的基本思想就是逐个比较相应位置的字符。

假设文本串为S，模式串为P：

1. 如果当前字符匹配成功（即S[i] == P[j]），则i++， j++，继续匹配下一个字符。

2. 如果失配（即S[i] != P[j]），令i = i - j + 1，j = 0，相当于每次匹配失败时，i回溯，j被置为0。

例如当文本串S = "BBC ABCDAB ABCDABCDABDE"，P = "ABCDABD"。

S[0]为B，P[0]为A，不匹配（情形2）。

然后再判断S[1]和P[0]是否匹配，相当于模式串向右移动一位。S[1]与P[0]还是不匹配（情形2）。

然后再判断S[2]和P[0]是否匹配，模式串再向右移动一位。直到S[4]与P[0]匹配成功（情形1）。

此时i = 5，j = 1，接下来判断S[5]与P[1]是否匹配。S[5]与P[1]匹配成功（情形1）。可得i = 6，j = 2。

直到S[10]为空格，P[6]为D，不匹配（情形2）。

此时i = 5，j = 0，相当于判断S[5]跟P[0]是否匹配。

至此可以看出，按照暴力匹配算法的思路。同理，直到找到匹配的字符串或文本串遍历结束退出。

BF暴力匹配在最坏情况下时间复杂度是$O(mn)$。

BF

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

int brute_force(const char *s, const char *p) {
    int s_len = strlen(s);
    int p_len = strlen(p);
    int i = 0;
    int j = 0;

    while (i < s_len && j < p_len) {
        if (s[i] == p[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == p_len) {
        return i - j;
    } else {
        return -1;
    }
}

int main(void) {
    const char *s = "BBC ABCDAB ABCDABCDABDE";
    const char *p = "ABCDABD";
    printf("%d\n", brute_force(s, p));
    return 0;
}

返回第一个完整匹配的起点下标，未找到返回-1，空模式串返回0。C/C++以字节为单位，Java以UTF-16代码单元为单位，Python以字符为单位；本节示例使用ASCII字符。