首页 > 编程 > JavaScript > 正文

JavaScript中数据结构与算法(四):串(BF)

2019-11-02 15:52:50
字体:
来源:转载
供稿:网友

   这篇文章主要介绍了JavaScript中数据结构与算法(四):串(BF),串是由零个或多个字符组成的有限序列,又叫做字符串,本文着重讲解了BF(Brute Force)算法,需要的朋友可以参考下

  串是由零个或多个字符组成的有限序列,又叫做字符串

  串的逻辑结构和线性表很相似的,不同的是串针对是是字符集,所以在操作上与线性表还是有很大区别的。线性表更关注的是单个元素的操作CURD,串则是关注查找子串的位置,替换等操作。

  当然不同的高级语言对串的基本操作都有不同的定义方法,但是总的来说操作的本质都是相似的。比如javascrript查找就是indexOf, 去空白就是trim,转化大小写toLowerCase/toUpperCase等等

  这里主要讨论下字符串模式匹配的几种经典的算法:BF、BM、KMP

  BF(Brute Force)算法

  Brute-Force算法的基本思想:

  从目标串s 的第一个字符起和模式串t的第一个字符进行比较,若相等,则继续逐个比较后续字符,否则从串s 的第二个字符起再重新和串t进行比较。

  依此类推,直至串t 中的每个字符依次和串s的一个连续的字符序列相等,则称模式匹配成功,此时串t的第一个字符在串s 中的位置就是t 在s中的位置,否则模式匹配不成功

  可见BF算法是一种暴力算法,又称为朴素匹配算法或蛮力算法。

  主串 BBC ABB ABCF

  子串 ABC

  在主串中找出子串的位置,对应了其实就是javascript的indexOf查找方法的实现了

  ?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 var sourceStr = "BBC ABB ABCF"; var searchStr = "ABC";   function BF_Ordinary(sourceStr, searchStr) { var sourceLength = sourceStr.length; var searchLength = searchStr.length; var padding = sourceLength - searchLength; //循环的次数 //BBC ABB ABCF =>ABC => 搜索9次 for (var i = 0; i <= padding; i++) { //如果满足了第一个charAt是相等的 //开始子循环检测 //其中sourceStr的取值是需要叠加i的值 if (sourceStr.charAt(i) == searchStr.charAt(0)) { //匹配成功的数据 var complete = searchLength; for (var j = 0; j < searchLength; j++) { if (sourceStr.charAt(i + j) == searchStr.charAt(j)) { --complete if (!complete) { return i; } } } } } return -1; }

  BF算法就是简单粗暴,直接把BBC ABB ABCF母串的每一个字符的下表取出来与模式串的第一个字符匹配,如果相等就进去字串的再次匹配

  这里值得注意:

  1:最外围循环的次数sourceLength - searchLength,因为我们匹配的母串至少要大于等于子串

  2:在子串的继续匹配中,母串的起点是需要叠加的(i+j)

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表