読者です 読者をやめる 読者になる 読者になる

【アルゴリズムの勉強】Rubyで力任せ探索で文字列探索を行うコードを書いてみる

力まかせ探索とは

力まかせ探索(ちからまかせたんさく、英: Brute-force search)またはしらみつぶし探索(英: Exhaustive search)は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。

力まかせ探索 - Wikipedia

Rubyで実装

def brute_force_search(str, target)
  str_location, target_location = 0, 0
  while str_location != str.length && target_location != target.length
    if str[str_location] == target[target_location]
      str_location += 1
      target_location += 1
    else
      str_location = str_location - target_location + 1
      target_location = 0
    end
  end
  if target_location == target.length
    return true
  else
    return false
  end
end

p brute_force_search("today", "day")
# => true
p brute_force_search("yesterday", "tomorrow")
# => false

参考文献、参考リンク