算法 57°C 25-12-2024

^{最近更新于：2024-12-25 17:42:39}

一、算法思想

BF算法的核心思想是“暴力搜索”，即通过遍历所有可能的解来找到满足条件的解。这种方法简单直接，但通常不够高效，适合小规模问题。

二、算法步骤

以字符串匹配为例，假设我们要在一个主字符串中查找一个子字符串（模式串）：

初始化指针：设置两个指针，分别指向主字符串和模式串的起始位置。
比较字符：逐个字符比较模式串与主字符串的对应字符。
找到匹配：

如果所有字符都匹配，记录下匹配位置。
如果有字符不匹配，移动主字符串的指针到下一个字符的位置，重新开始比较。

重复以上步骤：直到主字符串的指针移动到结束位置，或者找到了所有的匹配。

接下来我们详细讲解BF算法在字符串匹配中的匹配过程。接下来将逐步分析如何查找模式串 pattern = "ababd" 在主字符串 text = "ababcabcabababd" 中的所有匹配位置。

匹配过程详细步骤

初始化

主字符串：text = "ababcabcabababd"
模式串：pattern = "ababd"
主字符串的长度 n = 15 ，模式串的长度 m = 5 。
用于存储匹配位置的列表 matches = []。

外层循环（遍历主字符串）

从主字符串的每个字符出发，直到 n - m（即 15 - 5 = 10），因为在到达此位置后，模式串无法完全匹配。

内层循环（比较字符）

对于每个位置 i （主字符串中的起始索引），我们会检查从该位置开始的子串是否与模式串匹配。

匹配过程演示：

1. 从主字符串的索引 0 开始

主串部分："ababc"
模式串："ababd"
比较：
text[0] = a 和 pattern[0] = a（匹配）
text[1] = b 和 pattern[1] = b（匹配）
text[2] = a 和 pattern[2] = a（匹配）
text[3] = b 和 pattern[3] = b（匹配）
text[4] = c 和 pattern[4] = d（不匹配）
结果：未找到匹配，移动到下一个索引。

2. 从主字符串的索引 1 开始

主串部分："babca"
比较：
text[1] = b 和 pattern[0] = a（不匹配）
结果：未找到匹配，移动到下一个索引。

3. 从主字符串的索引 2 开始

主串部分："abcab"
比较：
text[2] = a 和 pattern[0] = a（匹配）
text[3] = b 和 pattern[1] = b（匹配）
text[4] = c 和 pattern[2] = a（不匹配）
结果：未找到匹配，移动到下一个索引。

4. 从主字符串的索引 3 开始

主串部分："bcabc"
比较：
text[3] = b 和 pattern[0] = a（不匹配）
结果：未找到匹配，移动到下一个索引。

5. 从主字符串的索引 4 开始

主串部分："cabca"
比较：
text[4] = c 和 pattern[0] = a（不匹配）
结果：未找到匹配，移动到下一个索引。

6. 从主字符串的索引 5 开始

主串部分："abcab"
比较：
text[5] = a 和 pattern[0] = a（匹配）
text[6] = b 和 pattern[1] = b（匹配）
text[7] = c 和 pattern[2] = a（不匹配）
结果：未找到匹配，移动到下一个索引。

7. 从主字符串的索引 6 开始

主串部分："bcaba"
比较：
text[6] = b 和 pattern[0] = a（不匹配）
结果：未找到匹配，移动到下一个索引。

8. 从主字符串的索引 7 开始

主串部分："cabab"
比较：
text[7] = c 和 pattern[0] = a（不匹配）
结果：未找到匹配，移动到下一个索引。

9. 从主字符串的索引 8 开始

主串部分："ababa"
比较：
text[8] = a 和 pattern[0] = a（匹配）
text[9] = b 和 pattern[1] = b（匹配）
text[10] = a 和 pattern[2] = a（匹配）
text[11] = b 和 pattern[3] = b（匹配）
text[12] = a 和 pattern[4] = d（不匹配）
结果：未找到匹配，移动到下一个索引。

10. 从主字符串的索引 9 开始

主串部分："babab"
比较：
text[9] = b 和 pattern[0] = a（不匹配）
结果：未找到匹配，移动到下一个索引。

11. 从主字符串的索引 10 开始

主串部分："ababd"
比较：
text[10] = a 和 pattern[0] = a（匹配）
text[11] = b 和 pattern[1] = b（匹配）
text[12] = a 和 pattern[2] = a（匹配）
text[13] = b 和 pattern[3] = b（匹配）
text[14] = d 和 pattern[4] = d（匹配）
结果：找到匹配，记录下匹配位置 10。

12. 结束搜索

当主字符串的指针达到 n - m 时停止，匹配过程结束。

最终结果

通过以上过程，我们可以找到的匹配位置为 [10]。

三、算法分析

时间复杂度

最坏情况下，BF算法的时间复杂度为 O(n×m)，其中 n 是主字符串的长度，m 是模式串的长度。这是因为在最坏情况下，可能需要对每个主字符串的字符进行 m 次比较。

空间复杂度

空间复杂度为 O(1)，只使用了常数级别的额外空间。

四、算法优缺点

优点：

简单易懂，容易实现。
在小规模问题上表现良好，可以保证找到最优解。

缺点：

随着问题规模的增大，时间复杂度通常会急剧上升，导致效率低下。
对于大规模问题，计算量可能会非常庞大，导致无法在合理时间内完成。

五、相关代码

下面是一个用C语言实现的BF算法进行字符串匹配的示例代码（即找出在文本text中第一次出现模式pattern的位置）：

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

void BF(const char *text,const char *pattern){
    int textlength=strlen(text);
    int patternlength=strlen(pattern);

    for(int i=0;i<=textlength-patternlength;i++){
        int j;
        for(j=0;j<patternlength;j++){
            if(text[i+j]!=pattern[j]){
                break;
            }
        }
            if(j==patternlength){
                printf("在第%d个字符处完成匹配\n",i+1);
            }
    }
}

int main()
{
    const char *text="ababcabcacbab";
    const char *pattern="abcac";
    BF(text,pattern);
    return 0;
}

代码分析

代码结构

头文件: #include <stdio.h> 和 #include <string.h> 用于标准输入输出和字符串处理。
函数 BF: 这是执行字符串匹配的核心函数，接收两个参数：text（待搜索的文本）和 pattern（待匹配的模式）。

函数逻辑

获取长度:
textlength 和 patternlength 分别存储文本和模式的长度。
外层循环:
for(int i=0; i<=textlength-patternlength; i++)：遍历文本的每个可能的起始位置。注意这里的条件为 i <= textlength - patternlength，否则会导致越界访问。
内层循环:
for(j=0; j<patternlength; j++)：逐字符比较文本和模式。如果当前字符不匹配，使用 break 跳出内层循环。
匹配成功:
如果内层循环完成时 j == patternlength，说明模式完全匹配，则输出匹配的位置（i+1，因为通常习惯使用1-based索引）。

主函数

初始化:
定义待匹配的文本 text 和模式 pattern。
调用:
通过调用 BF(text, pattern) 来执行匹配过程。

注意事项

越界检查:

外层循环的条件是 i <= textlength - patternlength，以避免越界访问。

匹配位置:

输出的位置使用了 1-based 索引，适合某些场合，但在程序内部处理时通常使用 0-based 索引。

性能:

该算法的时间复杂度为 O(n×m)，其中 m 是文本长度，n 是模式长度，效率较低，尤其在长文本或长模式的情况下。

评论留言

欢迎您，！您可以在这里畅言您的的观点与见解！

0 条评论

BF算法

一、算法思想

二、算法步骤