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

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;
}

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;
}

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;
        }

    }
}