ソフトⅡコース担当 ブログのおにーさまこと高橋です。
昨日に続き、今日も情報処理技術者試験午後解説です。今日は、平成27年度秋期基本情報技術者試験午後問8の解説です。Boyer-Moore-Horspool法を用いた文字列検索のアルゴリズム問題です。配列Skipの作成と、それを用いた移動が重要です。
設問1
プログラムの説明(2)に、配列Skipの内容と設定方法が記されています。この説明によると、Skipには、照合が失敗したときに次の照合のためにどれだけ移動するか、照合範囲の末尾の文字ごとの移動量を設定します。その方法は
- 探索文字列の末尾の文字と探索文字列にない文字は、探索文字列長(PatLen)にします
- 探索文字列の末尾以外の文字は、検索文字列の末尾からの文字数-1にします。ただし、複数回現れる場合は、最も末尾に近い文字で設定します。
設問2の文字列（図4）を使って設定する場合、次の図のようになります。
（画像をクリックで拡大）
初期値は探索文字列長にし、探索文字列中にある文字に対して値を設定します。文字列の前から処理すると、同じ文字の場合、後の文字の設定が上書きするので、最も末尾に近い文字の値が残ります。空欄aは「探索文字列長」、空欄bは「末尾からの文字数-1」です。空欄aの正解はエ、bの正解はカです。
設問2
図4の文字列に対して検索を行うと次の図になります。Skipの内容は、設問1の解説の通りです。
（画像をクリックで拡大）
αは、照会する最初の位置（比較範囲の右端位置）を設定する処理です。図では水色矢印の開始位置の設定です。水色矢印は3本あるので、3回実行することになります。水色矢印は3本あるので、3回実行することになります。空欄cの正解はアです。
βは、比較した文字列が等しいときに、比較範囲の先頭であるか（すべて一致したか）のチェック部分です。図では、黒の両端矢印が比較です。点線は一致しなかったときで、実線が一致したときです。この実線の時に先頭かの確認をするので、回数は実線の数7になります。空欄dの正解はオです。
返却値は9で、空欄eの正解はキです。
設問3
γの処理を、後ろからの繰り返しに変更すると、Skip設定時に、同じ文字の場合最も先頭に近い文字の値が残ります。すると、移動量が大きくなるので、検索文字列が含まれていてもチェックから漏れてしまう可能性があります。
（画像をクリックで拡大）
空欄fの正解はイです。
2015年（平成27年度）秋期の解説
- 平成27年度 秋 基本情報技術者試験 【問1】
- 平成27年度 秋 基本情報技術者試験 【問8】
- 平成27年度 秋 基本情報技術者試験 【問7】
- 平成27年度 秋 基本情報技術者試験 【問6】（その2）
- 平成27年度 秋 基本情報技術者試験 【問6】（その1）
- 平成27年度 秋 基本情報技術者試験 【問5】
- 平成27年度 秋 基本情報技術者試験 【問3】
- 平成27年度 秋 基本情報技術者試験 【問4】（その2）
- 平成27年度 秋 基本情報技術者試験 【問4】（その1）
- 平成27年度 秋 基本情報技術者試験 【問12】
- 平成27年度 秋 基本情報技術者試験 【問2】
- Date：
- この記事を
友だちに教える - LINE
- - HatenaBookmark
- GooglePlus
