平成27年度秋季基本情報午後問8

平成27年度秋季 基本情報技術者試験(FE)の午後問題8は、

• Boyer-Moore-Horspool法(BM法)を用いて、文字列検索を行うプログラム

に関する問題でした。

• 問題 : 2015h27a_fe_pm_qs.pdf

プログラム例(h27a_fe_pm8.c)

実行結果

本問で紹介されているボイヤー-ムーア文字列検索アルゴリズム(bmmatch関数)がどれ位高速に動作するのか、効率の悪い方法(naivematch関数)と比較してみました。

検索文字列の長さを8000000文字とし、その末尾に検索文字列("THISISAPEN")を連結して、検索文字列の最後でマッチするようにし、実行した結果が以下です。上段がBM法、下段が効率の悪いアルゴリズムの結果です。

今回の実験では、BM法が約3倍高速に動作していることが分かりました。検索文字列を長くするなど、条件を変えるともっと性能差が現れるような気がします。

$ gcc h27a_fe_pm8.c && ./a.out
7999989 0.010095[s]
7999989 0.028534[s]
$ ./a.out
7999989 0.010078[s]
7999989 0.028884[s]
$ ./a.out
7999989 0.010046[s]
7999989 0.028848[s]