文字列探索(1)
10月 25th, 2008 admin Posted in Ruby, アルゴリズムとデータ構造 | 
久しぶりに「アルゴリズムとデータ構造シリーズ」です。今回は第9章「浮動小数点数と数値計算」です。
文字列探索
このアルゴリズムについては説明は必要ないでしょうね。文字列の探索はコンピュータがビジネスに欠かせなくなってしまった今日では非常に重要になっています。
第2章のあたりでサーチについては学びましたが、効率の良いバイナリサーチは文字列探索の場合はつかえません。なぜならバイナリサーチはあらかじめサーチ対象をソートしておく必要があったからです。
では、どのような方法があるのでしょうか。この章は３つぐらいコードが必要で正直面倒ですが順番にやっていきたいと思います。
まず今回はもっとも単純ですが、単純がゆえにバグもおこりにくいということから最も使われているアルゴリズムからです。ようするに最初から順番に調べていくという方法です。
RUBY:
-
def simple_search(text,pattern)
-
text.length.times do |n|
-
print " text:" + text + "\npattern:"
-
print " " * n
-
print pattern
-
-
flag = true
-
pattern.length.times do |i|
-
flag = false if (pattern[i] != text[n + i])<span id="more-248"></span>
-
end
-
next if flag == false
-
return n
-
end
-
return -1
-
end
-
-
-
-
text = ARGV[0]
-
pattern = ARGV[1]
-
-
unless simple_search(text, pattern) == -1
-
p 'found'
-
else
-
p 'not found'
-
end
まとめ
短い文章の検索ならこれで十分ということでしょうね。
次回からは別のアルゴリズム2つに挑戦します。
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
11月 11th, 2008 at 2:27:31
[...] 文字列探索(1) [...]