当前位置：首页 > article >正文

暴力匹配算法 (BF)：字符串匹配算法的演进之路

article 2024/10/27 21:20:34

一、基本概念

二、功能

三、深度剖析

1. 算法原理

2. 算法流程

3. 代码实现

四、算法复杂度

五、算法优势

六、算法局限性

七、应用场景

八、总结

一、基本概念

BF算法，也称为朴素字符串匹配算法，是一种简单的字符串匹配算法，其核心思想是在文本串中逐个字符地比较模式串，直到找到匹配的位置或遍历完文本串。

二、功能

BF算法的主要功能是：

在一个文本串中查找模式串的出现位置。
返回模式串在文本串中所有出现位置的起始索引。

三、深度剖析

1. 算法原理

BF算法的原理非常直观：

从文本串的第一个字符开始，与模式串的第一个字符进行比较。
如果匹配，则继续比较下一个字符。
如果不匹配，则将模式串向后移动一位，从文本串的下一个字符开始重新比较。
重复以上步骤，直到找到匹配的位置或遍历完文本串。

2. 算法流程

BF算法的流程如下：

初始化： 设置两个指针 i 和 j，分别指向文本串和模式串的起始位置。
循环匹配：
- 如果 text[i] 和 pattern[j] 相等，则 i 和 j 都向后移动一位。
- 如果 text[i] 和 pattern[j] 不相等，则将模式串向后移动一位，即 j 指针重置为 0，i 指针指向下一个字符。
判断匹配： 当 j 指针到达模式串的末尾时，表示匹配成功，返回 i - j 作为匹配位置的起始索引。
循环结束： 如果 i 指针遍历完文本串，则表示没有匹配到模式串。

3. 代码实现

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

void BFMatch(char* text, char* pattern) 
{
    int N = strlen(text);
    int M = strlen(pattern);

    int i = 0; // 文本串指针
    int j = 0; // 模式串指针

    while (i < N) 
    {
        if (text[i] == pattern[j]) 
        {
            i++;
            j++;
            if (j == M) 
            {
                printf("模式串出现于索引 %d\n", i - j);
                j = 0; // 重置模式串指针
            }
        } 
        else 
        {
            i++;
            j = 0; // 重置模式串指针
        }
    }
}

int main() 
{
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";

    BFMatch(text, pattern);

    return 0;
}