次のプログラムの説明及びプログラムを読んで，設問１〜３に答えよ。
〔プログラムの説明〕
関数 BitapMatch は，Bitap 法を使って文字列検索を行うプログラムである。
Bitap 法は，検索対象の文字列（以下，対象文字列という）と検索文字列の照合に， 個別の文字ごとに定義されるビット列を用いるという特徴をもつ。
なお，本問では，例えば２進数の 16 ビット論理型の 定数 ØØØØØØØØØØØ1Ø1Ø1は， 上位の Ø を省略して“1Ø1Ø1”B と表記する。
(1) 関数 BitapMatch は，対象文字列を Text[] に，検索文字列を Pat[] に格納して呼び出す。 配列の要素番号は 1 から始まり，Text[] の i 番目の文字は Text[i] と表記する。 Pat[] についても同様に i 番目の文字は Pat[i] と表記する。対象文字列と検索文字列は， 英大文字で構成され，いずれも最長 16 文字とする。
対象文字列 Text[] が“AACBBAACABABAB”，検索文字列 Pat[] が“ACABAB”の場合の格納例を， 図１に示す。
図１ 対象文字列と検索文字列の格納例
(2) 関数 BitapMatch は，関数 GenerateBitMask を呼び出す。
関数 GenerateBitMask は，文字“A”〜“Z”の文字ごとに，検索文字列に応じた ビット列（以下，ビットマスクという）を生成し，要素数 26 の 16 ビット論理型配列 Mask[] に格納する。 Mask[1] には文字“A”に対するビットマスクを，Mask[2] には文字“B”に対するビットマスクを格納する。 このように Mask[1] 〜 Mask[26] に文字“A”〜“Z”に対応するビットマスクを格納する。
関数 GenerateBitMask は，Mask[] の全ての要素を“Ø”B に初期化した後， 1 以上で Pat[] の文字数以下の全ての i に対して，Pat[i] の文字に対応する Mask[] の要素で ある Mask[Index(Pat[i])] に格納されている値の，下位から数えて i 番目のビットの値を 1 にする。
関数 Index は，引数にアルファベット順で n 番目の英大文字を設定して呼び出すと， 整数 n（ 1 ≦ n ≦26 ）を返す。
(3) 図１で示した，Pat[] が“ACABAB”の例の場合，関数 GenerateBitMask を実行すると， Mask[] は図２のとおりになる。
図２ 図１で示した Pat[] に対する Mask[] の値
(4) 関数 GenerateBitMask の引数と返却値の仕様は，表１のとおりである。
〔プログラム１〕
| 設問１ | プログラムの説明及びプログラム１中の に入れる正しい答えを ， 解答群の中から選べ。 |
a に関する解答群
b に関する解答群
イ “1”B
ウ “1”B を PatLen ビットだけ論理左シフトした値
エ “1”B を ( PatLen −1 ）ビットだけ論理左シフトした値
オ “1111111111111111”B
c に関する解答群
イ “1”Bを i ビットだけ論理左シフトした値
ウ “1”Bを（ PatLen− 1 ）ビットだけ論理左シフトした値
エ “1”Bを PatLen ビットだけ論理左シフトした値
オ “1”B
〔関数 BitapMatch の説明〕
(1) Text[] と Pat[] を受け取り，Text[] の要素番号の小さい方から Pat[] と一致する文字列を検索し， 見つかった場合は，一致した文字列の先頭の文字に対応する Text[] の要素の要素番号を返し，見つからなかった場合は，−1 を返す。
(2) 図１の例では，Text[7] 〜 Text[12] の文字列が Pat[] と一致するので，7 を返す。
(3) 関数 BitapMatch の引数と返却値の仕様は，表２のとおりである。
〔プログラム２〕
設問２ 次の記述中の に入れる正しい答えを，解答群の中から選べ。
図１で示したとおりに，Text[] と Pat[] に値を格納し，関数 BitapMatch を実行した。 プログラム２の行βを実行した直後の変数 i と配列要素 Mask[Index(Text[i])] と変数 Status の値の遷移は， 表３のとおりである。
例えば，i が 1 のときに行βを実行した直後の Status の値は“1”B であることから， i が 2 のときに行αを実行した直後の Status の値は， “1”B を 1 ビットだけ論理左シフトした“1Ø”Bと“1”B とのビットごとの論理和を取った “11”B となる。次に，i が 2 のときに行βを実行した直後の Status の値は， Mask[Index(Text[2])] の値が“1Ø1Ø1”B であることを考慮すると，d となる。
同様に，i が 8 のときに行βを実行した直後の Status の値が“1Ø”B であるということに留意すると， i が 9 のときに行αを実行した直後の行βで参照する Mask[Index(Text[9])] の値は e であるので， 行βを実行した直後の Status の値は f となる。
配列要素 Mask[Index(Text[i])] と変数 Status の値の遷移
d 〜 f に関する解答群
オ “1ØØ”B カ “1Ø1”B キ “1Ø1Ø1”B
設問３ 関数 GenerateBitMask の拡張に関する， 次の記述中の に入れる正しい答えを， 解答群の中から選べ。ここで，プログラム３中の d には， 設問１の b の正しい答えが 入っているものとする。
表４に示すような正規表現を検索文字列に指定できるように，関数 GenerateBitMask を拡張し， 関数 GenerateBitMaskRegex を作成した。
〔プログラム３〕
g，i に関する解答群
h に関する解答群
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
