BF算法学习

发表于 | 分类于 | | 阅读次数:

BF 算法

Brute-Force 算法， 是一种简单朴素的模式匹配算法，常用于在一个主串内查找一个子串的问题
依据解题思路
假设主串 S 和子串 T， 子串长度 M， 主串长度 N， 0 < M <= N

  1. 先比较 S[1]和 T[1], 如果相同，继续比较 S[2]和 T[2], 直到 M
  2. 如果不同，指针移动至 S[2],再重复第一次的比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function findSubArrayStartIndex(total, part) {
  var size = total.length,
    matched_size = part.length;
  for (let i = 0; i < size; i++) {
    const tmp1 = total.slice(i, matched_size + i);
    if (isMatched(tmp1, part)) return i;
  }
  return -1;
}

function isMatched(part1, part2) {
  if (part1.length !== part2.length) return false;
  const size = part1.length,
    flg = false;
  for (let i = 0; i < size; i++) {
    if (part1[i] !== part2[i]) {
      flg = false;
      break;
    }
    if (i === size - 1) flg = true;
  }
  return flg;
}

在匹配失败时，主串的回溯的操作会影响效率，这种简单丢弃匹配信息的算法是其低效的原因。

参考自https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485906&idx=1&sn=f00a07cbca83d345cbacc327e335de2d&chksm=fa0e6653cd79ef45a9566cd8ea947d122cfde8e1c9459332e4d7d04f06644fc7a6e81da7ee10&scene=0&xtrack=1&key=034516426b2066d034c7c1b29870ede14e8a92b4535b464417555eba97ffe9cb08b0adf1bed2cd2cacdd73d13e652ee5856b3c801071439294a57ca6c1dabaa8bf97d0b015a0f622d6a99a12f2aa990d&ascene=1&uin=MjgyMTkzMDA4NA%3D%3D&devicetype=Windows+10&version=62060833&lang=zh_CN&pass_ticket=2s0OQl6S2cyRyPHwnDgNJKM3678%2F2wSuNoGHFaGq9qSejQtHFU3wZMAHfkIJm5Wr