[問題文・解答]
平成２７年度１０月に実施された基本情報技術者試験の午後試験の問題・解答はIPA公式ページからダウンロード出来ます。（以下リンク）
[問題概要]
この問題は必須問題です。
出題分野はデータ構造及びアルゴリズムで、問題の題材はBoyer-Moore-Horspool法を用いた文字列検索です。
Boyer-Moore-Horspool法を用いて検索文字列中に対象文字列があるかどうかを照合していく文字列検索プログラムについて問われます。専門知識はさほど必要ありませんが、問題文からプログラムの構造をよく理解する必要があり、難易度はやや高めの問題です。
出題分野はデータ構造及びアルゴリズムで、問題の題材はBoyer-Moore-Horspool法を用いた文字列検索です。
Boyer-Moore-Horspool法を用いて検索文字列中に対象文字列があるかどうかを照合していく文字列検索プログラムについて問われます。専門知識はさほど必要ありませんが、問題文からプログラムの構造をよく理解する必要があり、難易度はやや高めの問題です。
[設問1]
a) 関数BMMatch内の処理のうち、１〜４行目は各アルファベットに対する移動量を配列Skip[]に設定しています。
P.35(2)①「検索文字列の末尾の文字Pat[PatLen]にだけ現れる文字と、検索文字列に現れない文字に対応する移動量は、PatLenである」との記述より検索文字列の1〜PatLen-1文字目に現れない文字に対する移動量はPatLenとなります。これを設定しているのが、プログラム内の１〜２行目に相当するため、aにはPatLenが当てはまります。従って「エ」が正解です。
b) ３〜４行目に相当するのはP.25(2)②の説明部分であり、Pat[1]〜Pat[PatLen]に現れる文字に対する移動量として、その文字が検索文字列Patの末尾から何文字目に現れるか数えた文字数から１減じた値を設定する部分です。Iは検索文字列の１文字目からPatLen-1まで昇順に大きくしていくインデックスなのでbに入るのは( PatLen + 1 - I ) -1 = PatLen - Iとなり「カ」が正解です。
ここで、P.25(2)②にある「複数回現れる場合は、最も末尾に近い文字に対応する移動量とする」の条件については、Iを１から大きくしていくため複数回現れる文字は最後に出てきたものに対応する移動量で上書きされるため満たしています。この点については、設問3でも問われます。
[答] a) エ b) カ
a) 関数BMMatch内の処理のうち、１〜４行目は各アルファベットに対する移動量を配列Skip[]に設定しています。
P.35(2)①「検索文字列の末尾の文字Pat[PatLen]にだけ現れる文字と、検索文字列に現れない文字に対応する移動量は、PatLenである」との記述より検索文字列の1〜PatLen-1文字目に現れない文字に対する移動量はPatLenとなります。これを設定しているのが、プログラム内の１〜２行目に相当するため、aにはPatLenが当てはまります。従って「エ」が正解です。
b) ３〜４行目に相当するのはP.25(2)②の説明部分であり、Pat[1]〜Pat[PatLen]に現れる文字に対する移動量として、その文字が検索文字列Patの末尾から何文字目に現れるか数えた文字数から１減じた値を設定する部分です。Iは検索文字列の１文字目からPatLen-1まで昇順に大きくしていくインデックスなのでbに入るのは( PatLen + 1 - I ) -1 = PatLen - Iとなり「カ」が正解です。
ここで、P.25(2)②にある「複数回現れる場合は、最も末尾に近い文字に対応する移動量とする」の条件については、Iを１から大きくしていくため複数回現れる文字は最後に出てきたものに対応する移動量で上書きされるため満たしています。この点については、設問3でも問われます。
[答] a) エ b) カ
P.35(2)①「検索文字列の末尾の文字Pat[PatLen]にだけ現れる文字と、検索文字列に現れない文字に対応する移動量は、PatLenである」との記述より検索文字列の1〜PatLen-1文字目に現れない文字に対する移動量はPatLenとなります。これを設定しているのが、プログラム内の１〜２行目に相当するため、aにはPatLenが当てはまります。従って「エ」が正解です。
b) ３〜４行目に相当するのはP.25(2)②の説明部分であり、Pat[1]〜Pat[PatLen]に現れる文字に対する移動量として、その文字が検索文字列Patの末尾から何文字目に現れるか数えた文字数から１減じた値を設定する部分です。Iは検索文字列の１文字目からPatLen-1まで昇順に大きくしていくインデックスなのでbに入るのは( PatLen + 1 - I ) -1 = PatLen - Iとなり「カ」が正解です。
ここで、P.25(2)②にある「複数回現れる場合は、最も末尾に近い文字に対応する移動量とする」の条件については、Iを１から大きくしていくため複数回現れる文字は最後に出てきたものに対応する移動量で上書きされるため満たしています。この点については、設問3でも問われます。
[答] a) エ b) カ
[設問2]
図4の例で照合する場合の手順は以下の通りです。
①Pat[]を左端からスタートし、Text[4]とPat[4]を比較し、"X"と"C"で不一致である。
②Text[4]の文字"X"に対応する移動量の値4だけPat[]を右側に移動し、Text[8]とPat[4]の比較に移る。
③Text[8]とPat[4]は共に"C"で一致する。
④Text[7]とPat[3]は共に"A"で一致する。
⑤Text[6]とPat[2]は共に"B"で一致する。
⑥Text[5]とPat[1]を比較し、"B"と"A"で不一致である。
⑦Text[8]の文字"C"に対応する移動量の値4だけPat[]を右側に移動し、Text[12]とPat[4]の比較に移る。
⑧Text[12]とPat[4]は共に"C"で一致する。
⑨Text[11]とPat[3]は共に"A"で一致する。
⑩Text[10]とPat[2]は共に"B"で一致する。
⑪Text[9]とPat[1]は共に"A"で一致する。
c) プログラムの５行目〜１４行目では、対象文字列のある位置（プログラム中のPLast）と文字列の末尾（Ppat）から先頭に向かって照合し、不一致の場合はSkipに設定した移動量に従ってPLastを後ろにずらして再度照合していきます。対象文字列の最後まで一致部分が無かった場合は-1を返し、途中で一致部分が見つかった場合は対象文字列中の一致部分の先頭文字のインデックスを返します。
αの部分は、対象文字列中のどこから照合を開始するかを設定する部分で初回も含めてPLastが更新されるたびに実行されます。従って、上記の照合手順のうち①②⑦で実行されるため「ア」の３回が適切です。
d) βの部分は、Text[]中の文字とPat[]中の文字の比較を行って一致した場合にPat[]の先頭文字まで来ているかどうかを判定する部分です。従って、上記の照合手順のうち、③④⑤⑧⑨⑩⑪で実行されるため「オ」の７回が正解です。
e) c)の説明で述べたように一致部分が見つかった場合は対象文字列中の一致部分の先頭文字のインデックスを返します。従って、9を返すため「キ」が正解です。
[答] c) ア d) オ e) キ
①Pat[]を左端からスタートし、Text[4]とPat[4]を比較し、"X"と"C"で不一致である。
②Text[4]の文字"X"に対応する移動量の値4だけPat[]を右側に移動し、Text[8]とPat[4]の比較に移る。
③Text[8]とPat[4]は共に"C"で一致する。
④Text[7]とPat[3]は共に"A"で一致する。
⑤Text[6]とPat[2]は共に"B"で一致する。
⑥Text[5]とPat[1]を比較し、"B"と"A"で不一致である。
⑦Text[8]の文字"C"に対応する移動量の値4だけPat[]を右側に移動し、Text[12]とPat[4]の比較に移る。
⑧Text[12]とPat[4]は共に"C"で一致する。
⑨Text[11]とPat[3]は共に"A"で一致する。
⑩Text[10]とPat[2]は共に"B"で一致する。
⑪Text[9]とPat[1]は共に"A"で一致する。
c) プログラムの５行目〜１４行目では、対象文字列のある位置（プログラム中のPLast）と文字列の末尾（Ppat）から先頭に向かって照合し、不一致の場合はSkipに設定した移動量に従ってPLastを後ろにずらして再度照合していきます。対象文字列の最後まで一致部分が無かった場合は-1を返し、途中で一致部分が見つかった場合は対象文字列中の一致部分の先頭文字のインデックスを返します。
αの部分は、対象文字列中のどこから照合を開始するかを設定する部分で初回も含めてPLastが更新されるたびに実行されます。従って、上記の照合手順のうち①②⑦で実行されるため「ア」の３回が適切です。
d) βの部分は、Text[]中の文字とPat[]中の文字の比較を行って一致した場合にPat[]の先頭文字まで来ているかどうかを判定する部分です。従って、上記の照合手順のうち、③④⑤⑧⑨⑩⑪で実行されるため「オ」の７回が正解です。
e) c)の説明で述べたように一致部分が見つかった場合は対象文字列中の一致部分の先頭文字のインデックスを返します。従って、9を返すため「キ」が正解です。
[答] c) ア d) オ e) キ
[設問3]
γの部分を、設問中の記述に変更するとP.35(2)②の「複数回現れる場合は、最も末尾に近い文字に対応する移動量とする」の条件に反することとなり、最も先頭に近い文字に対応する移動量となります。つまり、本来の移動量より大きく移動してしまいます。
例えば、図3の例では照合手順⑤で文字"A"に対応する移動量が1ではなく3となるため、一致部分である6〜9文字目の部分を飛ばして、8〜11文字目を照合対象としてしまいます。従って、対象文字列中に、検索文字列が含まれているのに、−１を返す場合があり、「イ」が正解です。
[答] f) イ
上記の解説は問題と解答を元に自分なりの考え方を記述しており、間違っている部分もあるかと思いますので、ご了承願います。また、誤りについては正しい考え方をご指摘・ご教授頂けると助かります。
例えば、図3の例では照合手順⑤で文字"A"に対応する移動量が1ではなく3となるため、一致部分である6〜9文字目の部分を飛ばして、8〜11文字目を照合対象としてしまいます。従って、対象文字列中に、検索文字列が含まれているのに、−１を返す場合があり、「イ」が正解です。
[答] f) イ
上記の解説は問題と解答を元に自分なりの考え方を記述しており、間違っている部分もあるかと思いますので、ご了承願います。また、誤りについては正しい考え方をご指摘・ご教授頂けると助かります。
0 件のコメント:
コメントを投稿