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

简介:

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

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

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

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

 


BF(Brute Force)算法

Brute-Force算法的基本思想:

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

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

1340093208_2836

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

 

 


 

主串 BBC ABB ABCF

子串 ABC

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

复制代码
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)

3:通过一个条件判断是否完全匹配complete,BBC ABB ABCF中,我们在ABB的时候就需要跳过去

 上面是最简单的一个算法了,代码上还有更优的处理,比如在自串的匹配上可以采取取反的算法

 

优化算法(一)

复制代码
function BF_Optimize(sourceStr, searchStr) {
    var mainLength   = sourceStr.length;
    var searchLength = searchStr.length;
    var padding      = mainLength - searchLength;
    for (var offset = 0; offset <= padding; offset++) {
      var match = true;
      for (var i = 0; i < searchLength; i++) {
        //取反,如果只要不相等
        if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
          match = false;
          break;
        }
      }
      if (match) return offset;
    }
    return -1;
}
复制代码

 我们不需要判断为真的情况,我们只要判断为假的情况就可以了,当子匹配结束后match没有被修改过的话,则说明此匹配是完全匹配

 

以上2种方法我们都用到了子循环,我们能否改成一个循环体呢?

其实我们可以看到规律,主串每次都只会递增+1,子串每次匹配也是从头开始匹配,所以我们可以改成一个while,控制下标指针就可以了

 

优化算法(二)

复制代码
function BF_Optimize_2(sourceStr, searchStr) {
  var i = 0,
      j = 0;

    while (i < sourceStr.length) {
        // 两字母相等则继续  
        if (sourceStr.charAt(i) == searchStr.charAt(j)) {
          i++;
          j++;
        } else { // 两字母不等则角标后退重新开始匹配  
          i = i - j + 1; // i 回退到上次匹配首位的下一位  
          j = 0; // j 回退到子串的首位  
        }

        if (j == searchStr.length) {
          return i - j;
        }

    }
}
复制代码

i就是主串的下标定位,j就是子串的下标定位

当主串子串相等的时候,就进入了子串的循环模式,当子循环的次数j满足子串长度时,就验证是完全匹配

当主串子串不相等的时候,就需要把主串的下标往后移一位,当然i的时候,因为可能经过子串的处理,所以需要i-j+1, 然后复位子串

 

具体我们可以看看代码比较

基于BF算法的四种结构,for/while/递归


BF也是经典的前缀匹配算法,前缀还包括KMP,我们可见这种算法最大缺点就是字符匹配失败指针就要回溯,所以性能很低,之后会写一下KMP与BM算法针对BF的的升级


本文转自艾伦 Aaron博客园博客,原文链接:http://www.cnblogs.com/aaronjs/p/4218650.html,如需转载请自行联系原作者

相关文章
|
2月前
|
算法 JavaScript 前端开发
LZH 算法的模拟实现,JavaScript 版本
LZH 算法的模拟实现,JavaScript 版本
|
2月前
|
存储 前端开发 JavaScript
JavaScript 中的 BLOB 数据结构的使用介绍
JavaScript 中的 BLOB 数据结构的使用介绍
|
2月前
|
JavaScript 前端开发
JavaScript一种新的数据结构类型Map
JavaScript一种新的数据结构类型Map
|
1月前
|
算法 JavaScript 前端开发
在JavaScript中实现基本的碰撞检测算法,我们通常会用到矩形碰撞检测,也就是AABB(Axis-Aligned Bounding Box)碰撞检测
【6月更文挑战第16天】JavaScript中的基本碰撞检测涉及AABB(轴对齐边界框)方法,常用于2D游戏。`Rectangle`类定义了矩形的属性,并包含一个`collidesWith`方法,通过比较边界来检测碰撞。若两矩形无重叠部分,四个条件(关于边界相对位置)均需满足。此基础算法适用于简单场景,复杂情况可能需采用更高级的检测技术或物理引擎库。
51 6
|
18天前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
25天前
|
存储 JavaScript 前端开发
JavaScript中的对象是数据结构,存储键值对,键为字符串,值可为任意类型,包括函数(作为方法)
【6月更文挑战第25天】JavaScript中的对象是数据结构,存储键值对,键为字符串,值可为任意类型,包括函数(作为方法)。
24 2
|
28天前
|
存储 JavaScript 前端开发
JavaScript中的数组是核心数据结构,用于存储和操作序列数据
【6月更文挑战第22天】JavaScript中的数组是核心数据结构,用于存储和操作序列数据。创建数组可以使用字面量`[]`或`new Array()`。访问元素通过索引,如`myArray[0]`,修改同样如此。常见方法包括:`push()`添加元素至末尾,`pop()`移除末尾元素,`shift()`移除首元素,`unshift()`添加到开头,`join()`连接为字符串,`slice()`提取子数组,`splice()`进行删除、替换,`indexOf()`查找元素位置,`sort()`排序数组。还有其他如`reverse()`、`concat()`等方法。
112 2
|
1月前
|
算法 JavaScript 前端开发
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
23 1
|
1月前
|
存储 JavaScript 前端开发
【经典算法】LeetCode350:两个数组的交集 II(Java/C/Python3/JavaScript实现含注释说明,Easy)
【经典算法】LeetCode350:两个数组的交集 II(Java/C/Python3/JavaScript实现含注释说明,Easy)
15 1
|
24天前
|
算法 JavaScript 安全
一篇文章讲明白JavaScript_提交表单和MD5算法密码加密
一篇文章讲明白JavaScript_提交表单和MD5算法密码加密
11 0