平成21年度秋期 応用情報技術者試験(AP)の午後問題2は文字列照合に関する問題でした。
文字列照合といったら、遥か昔、学生時代に
といったアルゴリズムがあるということは習って知っていましたが、パターン文字列の情報を利用して効率よくスキップするということ位しか理解できていませんでしたので、今回はいい学習の機会となりました。
h21a_ap_pm2.rb
実行結果
問題では、以下の2種類が示されています。
- 方法1は、単純な照合方法
- 方法2は、効率的な照合方法(クヌース–モリス–プラット法)
今回は、
- 方法3として、効率的な照合方法(ボイヤー-ムーア法)
も加えて速度比較を行って見ました。
英大文字、小文字から長さ100万のランダムなテキストを生成し、パターンは生成したテキストの末尾300文字を設定しています。
実行結果は以下の通りです。方法1の単純な照合方法の遅さも際立っていますが、方法2に比して、方法3のボイヤー-ムーア法の効率の良さも際立つ結果となりました。
$ ruby h21a_ap_pm2.rb
user system total real
Naive 999700
0.720000 0.010000 0.730000 ( 0.729970)
Knuth–Morris–Pratt 999700
0.190000 0.000000 0.190000 ( 0.187722)
Boyer-Moore 999700
0.010000 0.000000 0.010000 ( 0.011079)
