C语言实现BF算法案例详解

什么是BF算法

BF算法是一种简单的字符串匹配算法，它的全称为Brute Force算法，中文翻译为暴力匹配算法。该算法的思想是对匹配串中与主串中的字符逐一进行比较，直到匹配成功或者不匹配结束。

实现BF算法的步骤

步骤一：暴力匹配

我们可以从主串的第一个字符开始，每次匹配一个字符，直到匹配成功或者匹配失败为止。如果匹配成功，就继续匹配下一个字符，如果匹配失败，就将主串的起始位置后移一位，再从起始位置开始匹配。

int index(char *s, char *t, int pos)
{
    int i = pos;    //i指向主串的起始位置
    int j = 1;      //j指向模式串的起始位置
    int s_len = strlen(s);
    int t_len = strlen(t);

    while (i <= s_len && j <= t_len) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            i = i - j + 2; //回溯到主串下一个位置
            j = 1;  //模式串从头开始匹配
        }
    }

    if (j > t_len) {
        return i - t_len;   //匹配成功，返回主串中匹配到的位置
    } else {
        return 0;   //匹配失败，返回0
    }
}

步骤二：功能封装

为了提高代码的重用性和可读性，我们可以将上述匹配功能封装成一个函数：

int match(char *s, char *t)
{
    int pos = 1; //从主串的第一个位置开始匹配

    while (pos) {
        pos = index(s, t, pos);

        if (pos > 0) {
            printf("匹配成功，匹配的位置为：%d\n", pos);
            pos++;
        }
    }

    if (pos == 0) {
        printf("匹配结束！\n");
    }
}

示例1：在一段文字中找出指定的单词

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

int index(char *s, char *t, int pos)
{
    int i = pos;
    int j = 1;
    int s_len = strlen(s);
    int t_len = strlen(t);

    while (i <= s_len && j <= t_len) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            i = i - j + 2;
            j = 1;
        }
    }

    if (j > t_len) {
        return i - t_len;
    } else {
        return 0;
    }
}

int match(char *s, char *t)
{
    int pos = 1;

    while (pos) {
        pos = index(s, t, pos);

        if (pos > 0) {
            printf("匹配成功，匹配的位置为：%d\n", pos);
            pos++;
        }
    }

    if (pos == 0) {
        printf("匹配结束！\n");
    }
}

int main()
{
    char str[] = "Hello World, I'm a programmer.";
    char word[] = "programmer";

    match(str, word);

    return 0;
}

输出结果为：

匹配成功，匹配的位置为：19

示例2：在一段程序代码中找出指定的函数调用

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

int index(char *s, char *t, int pos)
{
    int i = pos;
    int j = 1;
    int s_len = strlen(s);
    int t_len = strlen(t);

    while (i <= s_len && j <= t_len) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            i = i - j + 2;
            j = 1;
        }
    }

    if (j > t_len) {
        return i - t_len;
    } else {
        return 0;
    }
}

int match(char *s, char *t)
{
    int pos = 1;

    while (pos) {
        pos = index(s, t, pos);

        if (pos > 0) {
            printf("匹配成功，匹配的位置为：%d\n", pos);
            pos++;
        }
    }

    if (pos == 0) {
        printf("匹配结束！\n");
    }
}

int main()
{
    char code[] = "int main() {\n    printf(\"Hello World!\");\n    return 0;\n}";
    char func[] = "printf";

    match(code, func);

    return 0;
}

输出结果为：

匹配成功，匹配的位置为：16

总结

BF算法虽然简单，但其时间复杂度在最坏情况下达到O(m*n)，其中m和n分别是主串和模式串的长度，因此当需要匹配的字符串较长时，该算法效率较低。然而，它在某些情况下仍然具有一定的实用价值，因此我们需要根据实际情况来选择使用合适的算法。