可视化讲解：什么是BF算法？

前言

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

概念介绍

  • 字符串：由零个或多个字符组成的有限序列

  • 空串：零个字符的串

  • 空格串：只包含空格的串

  • 空串和空格串的区别

    • 空格串是有长度的，并且可以不止一个空格

    • 空串是没有长度的

  • 子串：串中任意个数的连续字符组成的子序列

  • 主串：包含子串的串

  • 子串在主串中的位置：子串的第一个字符在主串中的序号

  • 串的存储结构

    • 顺序存储结构

    • 链式存储结构

  • BF算法：Brute-Force算法，是一种简单朴素的模式匹配算法，常用于在一个主串S内查找一个子串T的出现位置

原理讲解

我们以主串为“toneornot”，模式串为"no"为例说明朴素模式匹配算法的实现原理

  1. 在未作任何操作时，此时效果如下图

    在这里插入图片描述

  2. 拿主串“toneornot”的第一位"t"与模式串第一位"n"相比较，不相等，此时效果如下图

    在这里插入图片描述

  3. 拿主串“toneornot”的第二位"o"与模式串第一位"n"相比较，不相等，此时效果如下图

    在这里插入图片描述

  4. 拿主串“toneornot”的第三位"n"与模式串第一位"n"相比较，相等，此时效果如下图

    在这里插入图片描述

  5. 拿主串“toneornot”的第四位"e"与模式串第二位"o"相比较，不相等，此时效果如下图

    在这里插入图片描述

  6. 拿主串“toneornot”的第四位"e"与模式串第一位"n"相比较，不相等，此时效果如下图

    在这里插入图片描述

  7. 拿主串“toneornot”的第五位"o"与模式串第一位"n"相比较，不相等，此时效果如下图

    在这里插入图片描述

  8. 拿主串“toneornot”的第六位"r"与模式串第一位"n"相比较，不相等，此时效果如下图

    在这里插入图片描述

  9. 拿主串“toneornot”的第七位"n"与模式串第一位"n"相比较，相等，此时效果如下图

    在这里插入图片描述

  10. 拿主串“toneornot”的第八位"o"与模式串第二位"o"相比较，相等，此时效果如下图。此时在主串中成功找到了模式串

    在这里插入图片描述

  11. 拿主串“toneornot”的第八位"o"与模式串第一位"n"相比较，不相等，此时效果如下图

    在这里插入图片描述

  12. 拿主串“toneornot”的第九位"t"与模式串第一位"n"相比较，不相等，此时效果如下图

    在这里插入图片描述

  13. 至此，在主串“toneornot”中成功找到了模式串"no"，位置为主串的第七位。

时间复杂度

  • 朴素的模式匹配算法最好情况下时间复杂度为O(1)。

  • 朴素的模式匹配算法平均时间复杂度为O(N+M)。其中N为主串长度，M为子串长度

  • 朴素的模式匹配算法最坏情况下时间复杂度为O((N-M+1)*M)。其中N为主串长度，M为子串长度

空间复杂度

  • 朴素的模式匹配算法平均空间复杂度为O(N+M)。其中N为主串长度，M为子串长度

算法优缺点

  • 优点：

    • 简单易懂

    • 易于理解

    • 某些应用场合效率较高

  • 缺点：

    • 需要多次回溯

    • 对于数据较大的文本文件而言效率极低

效果展示

在这里插入图片描述

更多算法学习请关注我的公众号

在这里插入图片描述

说明

  • 在公众号中回复“算法源码”即可获取十大经典算法源码

  • 在公众号中回复“算法书籍”即可获取经典入门算法书籍

  • 在公众号中回复“数据结构”即可获取数据结构相关源码

以上是 可视化讲解：什么是BF算法？ 的全部内容， 来源链接： utcz.com/a/35383.html

回到顶部