前言

BF 算法中的 BF 是 Brute Force 的缩写，中文叫暴力匹配算法，也叫朴素算法，他的方式很简单，也应用非常广泛。

概念解读

主串

被检索匹配的的字符串

模式串

要求匹配的字符串

算法解读

前提，主串的长度必须大于等于模式串，所以如果说主串的长度为n,模式串的长度为n.那么n>m.

基本思路为从第一位开始向后截取m位，然后与模式串进行比较，如果都符合，那么存在，如果不符合，那么向后移动一位。

image.png

你可以参考我的代码：https://codepen.io/robinson90/pen/LYPLwRX

  1. const bf=function(target,pattern){
  2.   let n = target.length, m=pattern.length;
  3.   if(n<m){
  4.     return false
  5.   }
  6.   let flag = false,targetArr=target.split(''),patternArr=pattern.split('');
  8.   for(let i=0,extra=n-m ;i<=extra;i++){
  9.     for(let j=0;j<m;j++){
  10.       if(targetArr[i+j] !== patternArr[j]){
  11.         break
  12.       }else if(j === m - 1){
  13.         flag = true
  14.         return flag
  15.        }
  16.     }
  17.   }
  18.   return flag  
  19. }

通过程序可以看出实际算法复杂度为(n-m)m,也就是nm。

当然从写法上我们可以优化一点，比如使用substring或者使用slice数组截取的方式将第二层循环解放。但为了方便对比，以及分析更复杂的情况，我们后续还是按照两层循环的方式去分析。

  1. // old codes
  2.   for(let j=0;j<m;j++){
  3.       if(targetArr[i+j] !== patternArr[j]){
  4.         break
  5.       }else if(j === m - 1){
  6.         flag = true
  7.         return flag
  8.       }
  9. }
  10. //new codes
  11. if(target.substring(i,i+m)===pattern){
  12.       return true
  13.  }

substring通识篇

也许肯定会有人说，为什么不直接用substring方法，那样就可以直接用字符串的相等来判断了，那么这里有必要科普下substring的实现原理是什么，我们找来了java6以及jdk7 版本的substring实现图解。

java jdk6 :

image.png

java jdk7 :
image.png

在代码中我们可以看到我们使用的substring其实也是使用的数组，在string新建对象的时候，就创建了这个值对应的数组，所以我们才可以通过下标，长度等实现方便的截取。

  1. public final class String
  2.     implements java.io.Serializable, Comparable<String>, CharSequence {
  3.     //JDK 6
  4.     String(int offset, int count, char value[]) {
  5.         this.value = value;
  6.         this.offset = offset;
  7.         this.count = count;
  8.     }
  10.     public String substring(int beginIndex, int endIndex) {
  11.         //check boundary
  12.         //关键就在这里传的value，这个value就是字符数组，新的字符串延用value，只是修改了属性值
  13.         return  new String(offset + beginIndex, endIndex - beginIndex, value);
  14.     }
  15. }

使用场景

虽然bf算法复杂度较高，但是比较简单，容易维护，所以在实际使用中应用非常广泛，主要原因有以下两个：

  1. 大部分的业务场景都是比较小的字符串检索，不会对整体性能有大的影响；
  2. bf算法本身简单，方便使用，错误率低，问题容易暴露，符合设计原则中的最小简单够用原则。