【Ruby】【アルゴリズム】BM法による文字列検索

今週末は目黒でRubyの集まりがあるみたいだ。

でもまだまだ。。この程度じゃだめだ。

BM法による文字列検索 とは

ボイヤー-ムーア文字列検索アルゴリズム（Boyer-Moore String Search Algorithm）は、効率的な文字列検索アルゴリズムの一種[1]。Robert S. Boyer と J Strother Moore が 1977年に開発した[2]。ボイヤー-ムーア法とも呼ばれる。
このアルゴリズムでは検索文字列（パターン）の前処理を行い、検索対象テキストの前処理は行わない。したがって、テキストについて何度も検索を行わない場合に適している

http://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%A4%E3%83%BC-%E3%83%A0%E3%83%BC%E3%82%A2%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

コード

def bm_search(text, pattern)
  cachTable = Array.new(256, pattern.length)
  _text = text.split("")
  _pattern = pattern.split("")

  _pattern.each_with_index do |ch, idx|
    #text_index をいくつずらして問題ないか を格納
    cachTable[ch.ord] = _pattern.length - idx - 1
  end
  
  text_index = _pattern.length - 1
  while text_index < _text.length

    pattern_index = _pattern.length - 1
    while _text[text_index] == _pattern[pattern_index]
      return text_index if pattern_index == 0
      text_index -= 1
      pattern_index -= 1
    end

    enable_step = cachTable[_text[text_index].ord]
    
    # text_indexをいくつ右にずらせるか > pattern_indexがいくつ左に進んだか
    if enable_step > _pattern.length - pattern_index
      text_index += enable_step
    else
      #pattern_indexが左に進んだ数のほうが大きい場合
      #text_indexを一つずらす
      text_index += _pattern.length - pattern_index
    end
  end
  -1
end

p bm_search("antennakana", "kana")
p bm_search("banana", "nan")

実行結果

7
2