文字列探索(1)
10月 25th, 2008 admin Posted in Ruby, アルゴリズムとデータ構造 | 2 Comments » 
久しぶりに「アルゴリズムとデータ構造シリーズ」です。今回は第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) [...]
11月 21st, 2010 at 4:18:44
Hi, - uncovered your web site accidentally whilst wandering across the net this evening, and glad that I did! I like the page structure and colours, but I have to say that I'm having difficulties when it loads. I'm using WannaBe 1 web browser for mac, and the footer would not line up properly. i am fairly certain employed precisely the same design on a company's online site, but the menu seems fine on mine. I think the problem is with my outdated browser & I'm assuming it's time to switch!