BM法をJS(JavaScript)で実装〜単語検索アルゴリズム〜

BM法とは

無駄な照合をせずに単語検索ができる。

やっていることは、ざっとこんな感じ。
1.keyの末尾文字から先頭方向に照合を行う。
2.textのt文字目からの照合処理で失敗（成功）した場合，text[t]の文字がkey内に存在する位置まで照合開始位置をスキップ数する。

BM法(Boyer-Moore法)

//スキップ関数
const bmSkip = (key, character) => {
  let index = 0;
  const reverseKey = key.split("").reverse().join("");
  if (reverseKey[0] == character) {
    index = reverseKey.indexOf(character, 1);
  } else {
    index = reverseKey.indexOf(character);
  }
  if (index < 0) {
    return reverseKey.length;
  } else {
    return index;
  }
};

//BM探索関数
const bmSearch = () => {
  const key = "abcaba"; //検索word
  const n = key.length; //検索wordの長さ
  let pos = key.length; //照合開始位置
  const text = "abcabcababcabaaojaoigjaojadkaoaoiddmxaiaakcabcabaiuhbaihiagaga"; //検索対象文字列
  let k = 0; //検索対象文字列の照合位置をずらす変数
  let j = 0; //検索wordの照合位置をずらす変数
  while (pos < text.length + 1) {
    if (text[pos - 1] == key[n - 1]) {
      k = pos - 1;
      j = n - 1;
      while (j > 0 && text[k] == key[j]) {
        k--;
        j--;
      }
      if (j == 0) {
        console.log("出現箇所先頭index" + (k + 1));
      }
    }
    pos = pos + bmSkip(key, text[pos - 1]);
  }
};

1文字ずつずらす単純な照合(Simple Search)

const normalSearch = () => {
  const key = "abcaba"; //検索word
  const n = key.length; //検索wordの長さ
  let pos = 0; //照合開始位置
  const text = "abcabcababcabaaojaoigjaojadkaoaoiddmxaiaakcabcabaiuhbaihiagaga"; //検索対象文字列
  let k = 0; //検索対象文字列の照合位置をずらす変数
  let j = 0; //検索wordの照合位置をずらす変数
  for (let i = 0; i < text.length - n; i++) {
    pos = i;
    j = 0;
    while (j < n && text[pos] == key[j]) {
      pos++;
      j++;
    }
    if (j == n) {
      console.log("出現箇所先頭index" + (pos - n + 1));
    }
  }
};