【アルゴリズムの勉強】Rubyで力任せ探索で文字列探索を行うコードを書いてみる
力まかせ探索とは
力まかせ探索(ちからまかせたんさく、英: Brute-force search)またはしらみつぶし探索(英: Exhaustive search)は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。
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