Boyer-Moore算法

基于《算法（第四版）》的Boyeer-Moore字符串查找算法实现的，只实现了坏字符（bad character）部分，好词缀（good suffix）部分没有实现。

Boyer-Moore算法也是基于回退的思路，还可以比KMP快很多。它是一种从右向左扫描模式串并将它和文本串匹配的算法。

以文本串”FINDINAHAYSTACKNEEDLE”和模式串”NEEDLE”为例。因为是从右向左与模式串进行匹配，首先回匹配模式字符串中的E和文本串中的N（位置为5的字符）。不匹配，因为字符N也出现在了模式串中，所以将模式串向右移动5位，将文本串中的字符N与模式串中的N对齐。然后比较模式串最右侧的E和文本串中的S（位置为10的字符），不匹配，且S不在模式串中，将模式串向右移动6位，继续匹配…

计算right[]

要启发式地处理不匹配的字符，需要使用数组right[]记录字母表中每个字符在模式串中出现的最靠右的下标（如果不存在则为-1），这个值揭示了如果该字符出现在文本中且在查找时造成了一次匹配失败，应该向右跳跃多远。

要计算right[]数组也很简单。初始化数组right[]时，所有元素的值设为-1，然后对于0到M-1的j，将right[pat.charCodeAt(j)]设置为j。

查找

计算玩right[]数组后，算法实现就很简单了。用一个索引i在文本串中从左向右移动，用另外一个索引j在模式串中从右向左移动。内循环会检查正文和模式串在位置i是否一致。如果从M-1到0的所有j，txt.charCodeAt(i + j)都和pat.charCodeAt(j)相等，那么就找到了一个匹配。否则匹配失败，那么会遇到三种情况：

• 如果造成不匹配的字符不包含在模式串中，将模式串向右移动j+1个位置（即i增加j+1）。因为相应字符不存在其right[]的值为-1，故移动的长度可表示为j - right[txt.charCodeAt(i + j)]。
• 如果造成不匹配的字符包含在模式串中，使用right[]数组将模式串和文本串对齐，使得该字符和它在模式串中出现的最右位置相匹配。移动的长度为j - right[txt.charCodeAt(i + j)]。
• 如果这种方法无法增大i，那就直接将i加1来保证模式串至少向右移动了一个位置。

代码实现

function search(pat, txt) {
  const M = pat.length
  const N = txt.length
  const right = getRight(pat)
  let skip = void 0
  // 指针i从左向右移动
  for (let i = 0; i <= N - M; i += skip) {
    skip = 0
    // 指针j从右向左移动
    for (let j = M - 1; j >= 0; j -= 1) {
      if (pat.charCodeAt(j) !== txt.charCodeAt(i + j)) {
        skip = Math.max(1, j - right[txt.charCodeAt(i + j)])
        break
      }
    }
    // 找到匹配
    // 匹配的话，是不会走if的逻辑，skip值不变为0
    // 而且如果不匹配，if逻辑保证了skip必定是大于等于1的
    if (skip === 0) return i
  }
  return -1 // 未找到匹配
  function getRight(pat) {
    const M = pat.length
    const R = 256
    const right = new Array(R).fill(-1)
    for (let j = 0; j < M; j += 1) {
      right[pat.charCodeAt(j)] = j
    }
    return right
  }
}