Boyer-Moore算法(javascript实现)

上一篇实现了一下kmp算法，但它不是字符串匹配效率最高的算法，目前大多数匹配采用的是效率更高的Boyer-Moore算法，具体的算法步骤可以看文章这里。那么来实现一下吧。

1.创建坏字符匹配表

function createBadCharMatch(search) {
  let map = {};
  let hash = {};
  for (let i = 0; i < search.length; i++) {
    if (hash[search[i]]) {
      map[i] = hash[search[i]];
    } else {
      map[i] = -1;
    }
    hash[search[i]] = i;
  }
  return map;
}

2.创建好后缀匹配表

function createGoodAfterMatch(search) {
  let map = { 0: 0 };
  let length = search.length;
  let i, j, k;
  let l = 0,
    r = 0;

  for (i = 1; i < length; ++i) {
    if (i >= r) {
      j = 0;
      k = i;
      map[i] = 0;

      while (k < length && search[j] == search[k]) {
        ++j;
        ++k;
      }

      if (k != i) {
        l = i;
        r = k - 1;
        map[i] = k - i;
      }
    } else {
      if (map[i - l] >= r - i + 1) {
        j = r - i + 1;
        k = r + 1;

        while (k < length && search[j] == search[k]) {
          ++j;
          ++k;
        }

        l = i;
        r = k - 1;
        map[i] = k - i;
      } else {
        map[i] = map[i - l];
      }
    }
  }
  return map;
}

3.开始比较,坏字符后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置,好后缀后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置,取两者的更大值。

function match(str, search) {
  let badCharMap = createBadCharMatch(search);
  let goodAfterMap = createGoodAfterMatch(search);

  let i1 = 0,
    i2 = 0;
  let len1 = str.length,
    len2 = search.length;
  while (i1 <= len1 - len2) {
    for (i2 = len2 - 1; i2 > -1; i2--) {
      if (str[i1 + i2] === search[i2]) {
        if (i2 === 0) {
          return [i1, i1 + len2];
        }
      } else {
        //坏字符
        //后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置
        let badNum = i2 - badCharMap[i2];
        //好后缀
        //后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置
        let goodNum = i2 - 1 - goodAfterMap[i2];
        i1 += Math.max(badNum, goodNum);
        break;
      }
    }
  }
}