【重学数据结构与算法(JS)】字符串匹配算法(一)——BF算法

作者 : 开心源码 本文共1518个字,预计阅读时间需要4分钟 发布时间: 2022-05-13 共151人阅读

前言

一切都要从 LeetCode 的第 28 题 实现 strStr()开始说起,当自己脑子里的第一种暴力查找法写出来并 AC 之后,还是觉得不满足,决定把能找到的解法都了解了,于是便有了这个系列。

字符串匹配的整体思路

当我了解完四种经典的匹配算法之后,总结了一下这类操作的核心:

  1. 模式串主串进行比较
    • 从前往后比较
    • 从后往前比较
  2. 匹配时,比较主串模式串的下一个位置
  3. 失配时,找到主串的一个合适位置重新开始与模式串的头部进行比较

所以总的来说,之所以会有这么多种匹配算法,本质上就是少量大神对第1步和第3步进行了优化,这个核心思路肯定要牢牢的先记在脑子里,这样之后了解优化的匹配算法就不会一脸懵逼。

算法详情与分析

详情

BF 算法,Brute-Force(暴力)法的简称,完全没有优化,每次失配时从主串的下一个位置进行比较,直到比较结束。

分析

算法形容如下:

  1. 模式串主串从前往后比较
  2. 匹配时,比较主串模式串的下一个位置
  3. 失配时,从主串下一个位置开始与模式串的头部重新开始比较

我们假设有 主串 ABABBBAAABABABBA模式串 ABABABB
下面放五张图来了解一下这个过程:

QQ20200112-160741.png

QQ20200112-161000.png

上面这两幅图,体现的是第1步和第2步,可以看出:

  1. S[0]P[0] 开始从头往后比较
  2. 假如匹配,比较S[i++]S[j++]

QQ20200112-161423.pngQQ20200112-161548.png

上面这两幅图,则体现的时第3步,可以看出:

  1. 假如 S[i]P[j] 失配
  2. j = 0P[0] 也就是模式串头部开始与主串下一个位置S[i - (j - 1)]开始继续进行匹配

重复上述两步,直到下图完全匹配或者者找不到模式串为止

QQ20200112-162337.png

代码

思路还是很好了解的,但是代码怎样写呢?
其实我一直觉得刷 LeetCode 除了巩固与提高数据结构与算法的能力之外,最重要的就是训练一种把思路翻译成代码的能力,下面我来尝试翻译一下上述的算法思路。

1、先进行极端情况的排除

carbon.png

这个操作应该是刷题刷多了,像以前做数学题写“解”的操作

2、写出整体的结构

  1. 从算法的思路很容易看出,这里的“重复上诉两步”,显著是要翻译成循环操作
  2. 假如是循环,那么终止条件是什么,可以很快想到,只有两种终止情况:
    • 主串中没有找到 模式串的匹配,此时 i = haystack.length
    • 主串中找到了模式串的匹配,此时 j = needle.length
  3. 算法解决过程主要是两步,所以这里肯定有一个分支结构
    • 匹配
    • 失配
  4. 假如没找到,直接 return -1 就好了,但要是找到了,应该怎样确定那个 index 的值呢?根据上面成功的图,我们可以发现,匹配的位置 8,是等于 主串的末尾 14 减去 模式串的末尾 6 得到的,也就是最后匹配的那个 index = i - j

carbon的副本.png

3、补充具体操作

根据算法分析里的形容,很容易知道

  1. 匹配,i++; j++; 比较各自的下一位
  2. 失配,i = i - (j - 1); j = 0;重新进行下一轮匹配

carbon的副本2.png

总结

至此,整个BF算法的分析与编写就完成了,尽管它是一个毫无优化的结构,但是表现出了所有字符串匹配算法的基本思想,计算机不是人,可以通过眼睛观察和大脑思考来进行定位,它只能通过一个一个字符的比较来进行判定,接下来的算法,就开始运用到少量骚操作来进行优化这个匹配的过程。

后记

“字符串匹配算法”是“重学数据结构与算法”系列笔记中的一个章节,细分为以下几个部分,之后会陆续填坑。

  • 字符串匹配算法(一)——BF算法
  • 字符串匹配算法(二)——KMP算法
  • 字符串匹配算法(三)——BM算法
  • 字符串匹配算法(四)——Sunday算法
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 【重学数据结构与算法(JS)】字符串匹配算法(一)——BF算法

发表回复