過去問を解いていく
令和元年秋期
設問
設問1
設問1-a
「設問1-a」は、 検索文字列が“ACABAB”(図1)の時に、図2の[ a ]に格納されるビット列を答える問題です。
文字列中の’A’と’C’について、図2に格納された’A’および’C’のビットマスク値との関係を下表に示します。
| 文字列 | ビットマスク値 |
|---|---|
A_A_A_ |
0・・・010101 |
_C____ |
0・・・000010 |
この表から、「文字列の左側からの並び」と「ビットマスク値の右側からの並び」とが対応していることが解ります。
’B’は、検索文字列“ACABAB”の左から4番目と6番目に存在しているので、ビットマスク値の右側から4番目と6番目が1となる、「イ. 0000000000101000」が正解となります。
ここで、推測できなくても問題ありません。
[ c ]に関する解答群を解く時にヒントが得られます。
設問1-a 再考参照
設問1-b,c
「設問1-b,c」は、 〔プログラム１〕中の穴埋め箇所に当てはまる処理を答える問題です。
記述抽出
本プログラムの処理詳細は、〔プログラムの説明〕の中に、以下のように記述されています。
関数 GenerateBitMask は、Mask[] の全ての要素を“0”Bに初期化した後、
1以上で Pat[] の文字数以下の全てのiに対して、Pat[i] の文字に対応する Mask[] の要素である Mask[Index(Pat[i])] に格納されている値の、下位から数えてi番目のビットの値を1にする。
対応付け
プログラムの処理詳細の記述を解析し、プログラムと対応付けします。
1以上で Pat[] の文字数以下の全てのiに対して、Pat[i] の文字に対応する Mask[] の要素である Mask[Index(Pat[i])] に格納されている値の、下位から数えてi番目のビットの値を1にする。
[ b ]について記述からの推定
プログラムの処理詳細の記述に適した処理を解答群から選び出します。
プログラムの処理詳細の記述に「“0”Bに初期化」と記述されているので、「ア. “0”B」が正解候補となります。
[ b ]についてプログラムからの推定
解答群から選択した処理をプログラムに適用し、矛盾がないことを確認します。
「ア. “0”B」を適用することで「Mask[] の全ての要素を“0”Bに初期化」できるので、「ア. “0”B」が正解となります。
[ c ]について記述からの推定
プログラムの処理詳細の記述に適した処理を解答群から選び出します。
1以上で Pat[] の文字数以下の全てのiに対して、Pat[i] の文字に対応する Mask[] の要素である Mask[Index(Pat[i])] に格納されている値の、下位から数えてi番目のビットの値を1にする。
理解力のある方ならこの記述内容を理解できるのでしょうが、残念ながら、私には理解できませんでした。 設問1-c 再考参照
そこで、プログラムから推定することとします。
[ c ]についてプログラムからの推定
解答群の各処理をプログラムに適用し、矛盾がないかを確認します。
（注：PatLenの値が6と仮定し、トレースします。）
Mask[Index(Pat[i])] ← “1”B OR Mask[Index(Pat[i])]
Mask[]の各要素(Mask[1]～Mask[26])に対し、“1”Bのみが設定されるので誤りとなります。
Mask[Index(Pat[i])] ← “100000”B OR Mask[Index(Pat[i])]
Mask[]の各要素(Mask[1]～Mask[26])に対し、“100000”Bのみが設定されるので誤りとなります。
Mask[Index(Pat[i])] ← “1000000”B OR Mask[Index(Pat[i])]
Mask[]の各要素(Mask[1]～Mask[26])に対し、“1000000”Bのみが設定されるので誤りとなります。
Mask[Index(Pat[i])] ← 1をiビットだけ論理左シフト OR Mask[Index(Pat[i])]
iは1以上なので最下位ビットをセットできません。よって、誤りとなります。
以上から、イ～オは除外され、「ア. “1”Bを(i－1)ビットだけ論理左シフトした値」が正解となります。
設問1-a 再考
「設問1-c」より、Mask[]には「“1”Bを(i－1)ビットだけ論理左シフトした値」が格納されることが分かりました。
文字列が“ACABAB”の時’B’は4文字目と6文字目に存在するので、
- 「“1”Bを(4－1)ビットだけ論理左シフトした値」
- 「“1”Bを(6－1)ビットだけ論理左シフトした値」
がセットされた、“101000”Bが Mask[2] に格納されます。
設問1-c 再考
プログラムの処理詳細の記述をプログラムに対応付けしやすいように、プログラムを書き換えてみます。
書き換え前
書き換え後
[ c ]の答えが分かった上で、プログラムの処理詳細の記述を解析し、プログラムと対応付けしてみます。
プログラムの処理詳細の記述にある「下位から数えてi番目のビットの値を1」が、「ア. “1”Bを(i－1)ビットだけ論理左シフトした値」に対応しているようです。
設問2
設問2-d,e,f
「設問2-d,e,f」は、 図1の状態で、プログラム２を実行し、行βを実行した直後の内部変数値を問う問題です。
プログラムの処理詳細は記述されていないので、地道にトレースを行っていきます。
トレース
[ d ]を求めるにあたっては、下記の記事を参考に地道にトレースしてみます。
例えば、iが1のときに行βを実行した直後の Status の値は“1”Bであることから、
iが2のときに行αを実行した直後の Status の値は、“1”Bを1ビットだけ論理左シフトした“10”Bと“1”Bとのビットごとの論理和を取った“11”Bとなる。
次に、iが2のときに行βを実行した直後の Status の値は、Mask[Index(Text[2])] の値が“10101”Bであることを考慮すると、[ d ]となる。
i=1の時
- i=1の時、対象文字列の1文字目(‘A’)が取り出され、’A’のマスク値であるMask[1]が参照されます。
- Mask[1]に設定されている値は、“10101”Bです。
| Status値 | |
|---|---|
| α実行前 | “0”B |
| α実行後 | “1”B ← “0<<1” or “1”B |
| β実行後 |
“1”B ← “1”B and “10101”B 行βを実行した直後の Status の値は“1”Bであることから、 |
i=2の時
- i=2の時、対象文字列の1文字目(‘A’)が取り出され、’A’のマスク値であるMask[1]が参照されます。
- Mask[1]に設定されている値は、“10101”Bです。
| Status値 | |
|---|---|
| α実行前 | “1”B |
| α実行後 |
“11”B ← “1<<1” or “1”B 行αを実行した直後の Status の値は、“1”Bを1ビットだけ論理左シフトした“10”Bと“1”Bとのビットごとの論理和を取った“11”Bとなる。 |
| β実行後 |
“1”B ← “11”B and “10101”B 行βを実行した直後の Status の値は、Mask[Index(Text[2])] の値が“10101”Bであることを考慮すると、[ d ]となる。 |
以上のトレースの結果、[ d ]は、「イ.“1”B 」が正解となります。
i=9の時
- i=9の時、対象文字列の1文字目(‘A’)が取り出され、’A’のマスク値であるMask[1]が参照されます。
- Mask[1]に設定されている値は、“10101”Bです。
よって、[ e ]は、「キ.“10101”B 」が正解となります。
[ f ]を求めるにあたっても、下記の記事を参考に地道にトレースしてみます。
iが8のときに行βを実行した直後の Status の値が“10”Bであるということに留意すると、
iが9のときに行αを実行した直後の行βで参照する Mask[Index(Text[9])] の値は[ e ]であるので、
行βを実行した直後の Status の値は[ f ]となる。
| Status値 | |
|---|---|
| α実行前 |
“10”B iが8のときに行βを実行した直後の Status の値が“10”Bであるということに留意すると |
| α実行後 |
“101”B ← “10<<1” or “1”B “10”Bを1ビットだけ論理左シフトした“100”Bと“1”Bとのビットごとの論理和を取った“101”Bとなる。 |
| β実行後 |
“101”B ← “101”B and “10101”B 行βを実行した直後の Status の値は[ f ]となる。 |
以上のトレースの結果、[ f ]は、「カ.“101”B 」が正解となります。
設問3
「設問3-g,h,i」は、 関数 GenerateBitMask を拡張し、関数 GenerateBitMaskRegex を作成した時の Mask[]配列の作られ方を問う問題です。
設問3-g
〔プログラム２〕のトレースでMask[]の使われ方を理解できていたら、〔プログラム３〕をトレースすることなく、問題を解くことができます。
〔プログラム２〕では、’A’の文字を検出したなら、’A’のマスク値 Mask[1]を参照し、文字位置に対応するビットがONかどうかで判断しています。
Mask[1]に設定されるマスク値は、’A’の存在する文字位置（1,3,4,5および6番目）に対応するビットがONとなればよいので、マスク値は“111101”Bとなります。
よって、[ g ]は「カ. “111101”B」が正解となります。
同様に、‘B’,‘C’に着目すると、’B’,’C’のマスク値は下表のようになります。
| 着目文字 | 着目文字列 | マスク値 |
|---|---|---|
| ‘A’ | “A_AAAA” | “111101”B |
| ‘B’ | "__B_B_" | “010100”B |
| ‘C’ | "_C__C_" | “010010”B |
設問3-h
表4の説明にあるように、[]内の文字は1文字として扱われるので、“AC[BA]A[ABC]A”は6文字として扱われます。
よって、[ h ]は「イ. 6」が正解となります。
プログラムをトレースすると、以下の条件時に文字数が＋１されています。
- ’[’検出時 (2箇所)
- ’[]’外(Mode=0)で文字を検出した時 (4箇所)
設問3-i
“AC[B[AB]AC]A”のように入れ子になっている場合、どのように扱えばいいのか定義されていないので、プログラムをトレースします。
全ロジックをトレースする必要はなく、
- “[”検出中に“[”を検出した場合
- “]”検出後に再度“]”を検出した場合
の処理をトレースします。
■ i: 1, ≦ OriginalPatLen, 1
｜▲ Pat[i] = "[" /*開始検出*/
｜｜• Mode ← 1 /*モードセット*/
｜｜• PatLen ← PatLen + 1 /*"["から"]"までの文字数を1と扱う*/
｜－－－－
｜｜▲ Pat[i] = "]" /*終了検出*/
｜｜｜• Mode ← 0 /*モードクリア*/
｜｜－－－－ /*開始/終了以外*/
｜｜｜▲ Mode = 0 /*"["から"]"までの文字をカウントアップしないことで左シフト数を同じくする*/
｜｜｜｜• PatLen ← PatLen + 1
｜｜｜▼
｜｜｜• Mask[Index(Pat[i])] ← "1"Bを(PatLen - 1)ビットだけ
｜｜｜ 論理左シフトした値とMask[Index(Pat[i])]とのビットごとの論理和
｜｜▼
｜▼
■（注：本プログラムは、“[[”と連続した場合を考慮されていません。）
"“[”検出中に“[”を検出した場合
| “[”検出 | Mode ← 1 PatLen ← PatLen + 1 |
論理左シフト数更新 |
| ’A’検出 | Mask[]更新 | |
| “[”検出 | Mode ← 1 PatLen ← PatLen + 1 |
論理左シフト数更新 |
“[”検出中に“["を検出した場合、"][”を検出したような処理となります。
“]”検出後に再度“]”を検出した場合
| “]”検出 | Mode ← 0 | |
| ’A’検出 | PatLen ← PatLen + 1 Mask[]更新 |
論理左シフト数更新 |
| “]”検出 | Mode ← 0 | 既にMode=0 |
“]”が連続した場合、最初の“]”でMode=0になり、後続の“]”でもMode=0としています。
以上より、“AC[B[AB]AC]A”は“AC[B][AB]ACA”と扱われ、
Mask[1]に設定されるマスク値は、’A’の存在する文字位置（1,4,5および7番目）に対応するビットがONとなればよいので、マスク値は“1011001”Bとなります。
[ i ]は「ウ. “1011001”B」が正解となります。
本文
次のプログラムの説明及びプログラムを読んで、設問1～3に答えよ。
〔プログラムの説明〕
関数 BitapMatch は、Bitap法を使って文字列検索を行うプログラムである。
Bitap法は、検索対象の文字列(以下、対象文字列という)と検索文字列の照合に、個別の文字ごとに定義されるビット列を用いるという特徴をもつ。
なお、本問では、例えば2進数の16ビット論理型の定数 0000000000010101 は、上位の0を省略して“10101”Bと表記する。
- 関数 BitapMatch は、対象文字列を Text[] に、検索文字列を Pat[] に格納して呼び出す。配列の要素番号は1から始まり、Text[] のi番目の文字は Text[i] と表記する。Pat[] についても同様にi番目の文字は Pat[i] と表記する。対象文字列と検索文字列は、英大文字で構成され、いずれも最長16文字とする。
対象文字列 Text[] が“AACBBAACABABAB”、検索文字列 Pat[] が“ACABAB”の場合の格納例を、図1に示す。
関数 BitapMatch は、関数 GenerateBitMask を呼び出す。 関数 GenerateBitMask は、文字“A”～“Z”の文字ごとに、検索文字列に応じたビット列(以下、ビットマスクという)を生成し、要素数26の16ビット論理型配列 Mask[] に格納する。Mask[1] には文字“A”に対するビットマスクを、Mask[2] には文字“B”に対するビットマスクを格納する。このように Mask[1]～Mask[26] に文字“A”～“Z”に対応するビットマスクを格納する。
関数 GenerateBitMask は、Mask[] の全ての要素を“0”Bに初期化した後、1以上で Pat[] の文字数以下の全てのiに対して、Pat[i] の文字に対応する Mask[] の要素である Mask[Index(Pat[i])] に格納されている値の、下位から数えてi番目のビットの値を1にする。
関数 Index は、引数にアルファベット順でn番目の英大文字を設定して呼び出すと、整数n(1≦n≦26)を返す。図1で示した、Pat[] が“ACABAB”の例の場合、関数 GenerateBitMask を実行すると、Mask[] は図2のとおりになる。
- 関数 GenerateBitMask の引数と返却値の仕様は、表1のとおりである。
〔プログラム１〕
設問1
プログラムの説明及びプログラム１中の [ ] に入れる正しい答えを、解答群の中から選べ。
a に関する解答群
- 0000000000000101
- 0000000000101000
- 0001010000000000
- 1010000000000000
b に関する解答群
- “0”B
- “1”B
- “1”BをPatLenビットだけ論理左シフトした値
- “1”Bを(PatLen－1)ビットだけ論理左シフトした値
- “1111111111111111”B
c に関する解答群
- “1”Bを(i－1)ビットだけ論理左シフトした値
- “1”Bをiビットだけ論理左シフトした値
- “1”Bを(PatLen－1)ビットだけ論理左シフトした値
- “1”BをPatLen ビットだけ論理左シフトした値
- “1”B
〔関数 BitapMatch の説明〕
- Text[] と Pat[] を受け取り、Text[] の要素番号の小さい方から Pat[] と一致する文字列を検索し、見つかった場合は、一致した文字列の先頭の文字に対応する Text[] の要素の要素番号を返し、見つからなかった場合は、-1を返す。
- 図1の例では、Text[7]～Text[12] の文字列が Pat[] と一致するので、7を返す。
- 関数 BitapMatch の引数と返却値の仕様は、表2のとおりである。
〔プログラム２〕
○整数型関数 : BitapMatch(文字型: Text[], 文字型: Pat[])
○16 ビット論理型: Goal, Status, Mask[26]
○整数型: i, TextLen, Pathen
• TextLen ← Text[] の文字数
• Pathen ← GenerateBitMask(Pat[], Mask[])
• Status ← "0"B
• Goal ← "1"B を (Pathen - 1) ビットだけ論理左シフトした値
■ i: 1, i ≤ TextLen, 1
｜• Status ← Status を 1ビットだけ論理左シフトした値と ←α
｜ "1"B とのビットごとの論理和
｜• Status ← Status と Mask[Index(Text[i])] とのビットごとの論理積 ←β
｜▲Status と Goal とのビットごとの論理積 ≠ "0"B
｜｜• return(i - PatLen + 1)
｜▼
■
• return (-1) 設問2
次の記述中の [ ] に入れる正しい答えを、解答群の中から選べ。
図1で示したとおりに、Text[] と Pat[] に値を格納し、関数 BitapMatch を実行した。プログラム２の 行β を実行した直後の変数iと配列要素 Mask[Index(Text[i])] と変数 Status の値の遷移は、表3のとおりである。
例えば、iが1のときに 行β を実行した直後の Status の値は“1”Bであることから、iが2のときに 行α を実行した直後の Status の値は、“1”Bを1ビットだけ論理左シフトした“10”Bと“1”Bとのビットごとの論理和を取った“11”Bとなる。次に、iが2のときに 行β を実行した直後の Status の値は、Mask[Index(Text[2])] の値が“10101”Bであることを考慮すると、dとなる。
同様に、iが8のときに 行β を実行した直後の Status の値が“10”Bであるということに留意すると、iが9のときに 行α を実行した直後の 行β で参照する Mask[Index(Text[9])] の値は [ e ] であるので、 行β を実行した直後の Status の値は [ f ] となる。
d、e、f に関する解答群
- “0”B
- “1”B
- “10”B
- “11”B
- “100”B
- “101”B
- “10101”B
設問3
関数 GenerateBitMask の拡張に関する、次の記述中の [ ] に入れる正しい答えを、解答群の中から選べ。ここで、プログラム３中の [ b ] には、設問1の [ b ] の正しい答えが入っているものとする。
表4に示すような正規表現を検索文字列に指定できるように、関数 GenerateBitMask を拡張し、関数 GenerateBitMaskRegex を作成した。
〔プログラム３〕
○整数型関数 : GenerateBitMaskRegex(文字型: Pat[],
16 ビット論理型: Mask[])
○整数型 : i, OriginalPatLen, PatLen, Mode
• OriginalPatLen ← Pat[] の文字数
• PatLen ← 0
• Mode ← 0
■ i: 1, ≦ 26, 1
｜• Mask[i] ← [ b ] /*初期化*/
■
■ i: 1, ≦ OriginalPatLen, 1
｜▲ Pat[i] = "["
｜｜• Mode ← 1
｜｜• PatLen ← PatLen + 1
｜－－－－
｜｜▲ Pat[i] = "]"
｜｜｜• Mode ← 0
｜｜－－－－
｜｜｜▲ Mode = 0
｜｜｜｜• PatLen ← PatLen + 1
｜｜｜▼
｜｜｜• Mask[Index(Pat[i])] ← "1"Bを(PatLen - 1)ビットだけ
｜｜｜ 論理左シフトした値とMask[Index(Pat[i])]とのビットごとの論理和
｜｜▼
｜▼
■
• return (PatLen)Pat[] に“AC[BA]A[ABC]A”を格納して、関数 GenerateBitMaskRegex を呼び出した場合を考える。この場合、文字“A”に対応するビットマスクである Mask[1] は [ g ] となり、関数 GenerateBitMaskRegex の返却値は [ h ] となる。また、Pat[] に格納する文字列中において[]を入れ子にすることはできないが、誤って Pat[] に“AC[B[AB]AC]A”を格納して関数 GenerateBitMaskRegex を呼び出した場合、Mask[1]は [ i ] となる。
g、i に関する解答群
- “1001101”B
- “1010100001”B
- “1011001”B
- “101111”B
- “110011”B
- “111101”B
h に関する解答群
- 4
- 6
- 9
- 13
