Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

平成21年度秋期応用情報午後問2

平成21年度秋期 応用情報技術者試験(AP)の午後問題2は文字列照合に関する問題でした。

文字列照合といったら、遥か昔、学生時代に

といったアルゴリズムがあるということは習って知っていましたが、パターン文字列の情報を利用して効率よくスキップするということ位しか理解できていませんでしたので、今回はいい学習の機会となりました。

h21a_ap_pm2.rb

実行結果

問題では、以下の2種類が示されています。

  • 方法1は、単純な照合方法
  • 方法2は、効率的な照合方法、ボイヤー-ムーア法でしょうか?

方法2がどの程度、効率的なのか速度比較を行ってみました。

英大文字、小文字から長さ100万のランダムなテキストを生成し、パターンは生成したテキストの末尾300文字を設定しています。

実行結果は以下の通りです。

$ ruby h21a_ap_pm2.rb
                      user     system      total        real
Naive           999700
  0.720000   0.010000   0.730000 (  0.728408)
Boyer-Moore     999700
  0.190000   0.000000   0.190000 (  0.186781)