今週の午後問題〔解答〕アルゴリズム Bitap 法による文字列検索 2019 (令和元) 年度

今週の午後問題は「 2019 年度 秋期 アルゴリズム」でしたが、皆さん、手応えはいかがでしょうか？

金曜になりましたので、出題の 解答 と 矢沢久雄さんによる 解説 に加えて、皆さんの正解率を公開します。

設問 1b　^※説明の都合で、空欄 a より先に空欄 b を取り上げます

正解 ア

プログラムの説明に

Mask[] のすべての要素を “0” B に初期化

とあり、それがプログラムの空欄 b に該当します。

さらに、プログラムに、

|　・Mask[i] ← b  /* 初期化 */

というコメントも付けられています。空欄 b の正解は、選択肢アです。

infoスマートフォンをご覧の際、プログラムは右にスクロールできます

設問 1c　^※説明の都合で、空欄 a より先に空欄 c を取り上げます

正解 ア

プログラムの説明を見ると、空欄 c に入るのは

下位から数えて i 番目のビットを 1 にした値

であり、

i が 1 なら

0000000000000001

i が 2 なら

0000000000000010

i が 3 なら

0000000000000100

・・・

と思われます。 0000000000000001 を i – 1 だけ左論理シフトすればよいでしょう。

ところが、プログラムを見ると

■ i: 1, i ≦ PatLen, 1
|　・Mask[Index(Pat[i])] ← c と
|                   Mask[Index(Pat[i])] とのビットごとの論理和
■

になっています。

具体例を見ると、”ACABAB” の先頭（i = 1）の “A” に対応するビットマスクが
0000000000000001 ではなく、
0000000000010101 になっています。

このことから、 “ACABAB” の中に “A” が 3 個あるので、それらを論理和で重ね合わせていることがわかります。

空欄 c は、0000000000000001 を i – 1 だけ論理左シフトするだけでなく、それまでに得られているビットマスクと論理和で重ね合わせるのです。したがって、正解は選択肢アです。

設問 1a

正解 イ

先に、空欄 b と空欄 c を解いたことで、ビットマスクを作る方法がわかりました。

空欄 a には、 “B” に対応するビットマスクが入ります。問題に示された “ACABAB” では、先頭から 4 番目と 6 番目に “B” が登場します。

したがって、
0000000000001000 と
0000000000100000 を論理和で重ね合わせた
0000000000101000 が “B” に対応するビットマスクです。

正解は、選択肢イです。

設問 2

正解d ― イ、 e ― キ、 f ― カ

プログラムを i = 1 ~ 9 までトレースすれば、空欄 d 、e 、f を埋められます。

変数の値をトレースするのは、 β の直後の値であることに注意してください。トレースした結果を以下に示します。

空欄 d 、空欄 e 、空欄 f の正解は、選択肢イ、選択肢キ、選択肢カです。

設問 3h　^※説明の都合で、空欄 g より先に空欄 h を取り上げます

正解 イ

Mode の初期値は 0 で、 Mode = 0 なら 1 文字処理するごとに PatLen の値を 1 増やしています。

“[” を処理すると、 PatLen を 1 増やし、 Mode を 1 にします。そして、 “]” を処理すると、 Mode を 0 に戻します。これは、 “[” と “]” で囲まれた部分では、その間に何文字あっても PatLen が 1 だけ増えるということです。

したがって、問題に示された “AC[BA]A[ABC]A” という具体例を処理したときの PatLen は、

“AC” で 2 増えて、
“[BA]” で 1 増えて、
“A” で 1 増えて、
“[ABC]” で 1 増えて、
“A” で 1 増えるので、

全部で 6 になります。

したがって、空欄 h の正解は、選択肢イです。

設問 3g

正解 カ

“AC[BA]A[ABC]A” において、 “A” は 5 回登場し、 “[” と “]” で囲まれた部分では、その間に何文字あっても PatLen が 1 だけ増えるのですから、 “ACAAAA” を想定してビットマスクを求めればよいことになります。

“A” は、 1 文字目、 3 文字目、 4 文字目、 5 文字目、 6 文字目に登場するので、それらの桁位置を 1 とした “111101” B というビットマスクになります。したがって、空欄 g の正解は、選択肢カです。

設問 3i

正解 ウ

誤って Pat[] に “AC[B[AB]AC]A” が与えられた場合には、 “[B[A” の部分で PatLen が 2 増えてしまうので、 “A” のビットマスクは、 “ACBAACA” を想定して求められます。

“A” は、 1 文字目、 4 文字目、 5 文字目、 7 文字目に登場するので、それらの桁位置を 1 とした “1011001” B というビットマスクになります。したがって、空欄 i の正解は、選択肢ウです。