ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

問4 並びの検索で比較が一致する回数

基本情報​技術者試験 令和7年度 公開問題 科目B、全6問のうちの問4。

出典：令和7年度 基本情報技術者試験 公開問題 科目B 問4（プログラムは原本の画像を文字に書き起こし、字下げは 1 段を空白 2 つで表した。空欄は［　　］で表した）

次の記述中の［　　］に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。

関数 search は，二つの文字型の配列を，それぞれ引数 data 及び key で受け取り，data から，key の要素の並びと同じ並びを全て探し，その先頭の要素番号を全て格納した配列を返す。見つからなければ，要素数 0 の配列を返す。

関数 search を search({"a", "b", "a", "b", "c", "a", "b", "c"}, {"a", "b", "c"}) として呼び出すと，/*** β ***/の行の条件式が真となる回数は［　　］回である。

〔プログラム〕
/* keyは，要素数1以上の配列である */
○整数型の配列: search(文字型の配列: data, 文字型の配列: key)
整数型: i, j, lenData, lenKey
整数型の配列: result ← {}  // 要素数0の配列
 
lenData ← dataの要素数
lenKey ← keyの要素数
 
/* (lenData － lenKey ＋ 1) が0以下のときは繰返し処理を実行しない */
for (i を 1 から (lenData － lenKey ＋ 1) まで 1 ずつ増やす)
for (j を 1 から lenKey まで 1 ずつ増やす)  // α
if (data[i ＋ j － 1] が key[j] と等しい)  /*** β ***/
if (j が lenKey と等しい)
resultの末尾 に iの値 を追加する
endif
else
αの行から始まる繰返し処理を終了する
endif
endfor
endfor
return result
  1. ア1
  2. イ2
  3. ウ3
  4. エ4
  5. オ5
  6. カ6
  7. キ7
  8. ク8
  9. ケ9
  10. コ1⁠0
答えと解説を開く

正解はクです。

lenData ＝ 8、lenKey ＝ 3 なので、i は 1 から 8 － 3 ＋ 1 ＝ 6 まで動きます。各 i で、j を 1 から 3 まで進めて data[i ＋ j － 1] と key[j] を比べ、違ったらその i をやめます。β の条件が真になるのは、比べた文字が同じだった回です。data は 1 から順に a、b、a、b、c、a、b、c、key は a、b、c です。i ＝ 1 では、data[1] ＝ a と key[1] ＝ a が同じ (1 回)、data[2] ＝ b と key[2] ＝ b が同じ (2 回)、data[3] ＝ a と key[3] ＝ c が違うので終わります。i ＝ 2 では、data[2] ＝ b と a が違い、0 回です。i ＝ 3 では、data[3] ＝ a、data[4] ＝ b、data[5] ＝ c が全部同じで 3 回 (累計 5 回)、j ＝ 3 で result に 3 を足します。i ＝ 4 は data[4] ＝ b、i ＝ 5 は data[5] ＝ c で、どちらも最初の比較で違い、0 回です。i ＝ 6 では、data[6] ＝ a、data[7] ＝ b、data[8] ＝ c が全部同じで 3 回 (累計 8 回)、result に 6 を足します。真になる回数は 2 ＋ 3 ＋ 3 ＝ 8 回で、戻り値は {3, 6} です。正解はクです。

ほかの選択肢が違う理由

  • ア1 回は少なすぎます。i ＝ 1 で a と b が一致する 2 回だけでも 1 回を超えます。
  • イ2 回は、見つかった並びの数 (i ＝ 3 と i ＝ 6) です。β は 1 文字ずつの比較なので、一致した文字の数を数えます。
  • ウ3 回は、key の長さ 1 回分です。完全に一致する並びは 2 か所あり、それだけで 6 回になります。
  • エ4 回は少なすぎます。i ＝ 3 と i ＝ 6 の完全一致だけで 6 回あります。
  • オ5 回は、i ＝ 1 の 2 回と i ＝ 3 の 3 回までで止めた数です。i ＝ 6 の 3 回が抜けています。
  • カ6 回は、完全に一致した 2 か所の 3 回ずつだけを数えた数です。i ＝ 1 で a と b まで一致した 2 回も β は真になります。
  • キ7 回は、i ＝ 1 の途中までの一致を 1 回と数えた数です。a と b の 2 文字が一致しているので 2 回です。
  • ケ9 回は多すぎます。i ＝ 1 は 3 文字目の a と c で違うので、真になるのは 2 回だけです。
  • コ1⁠0 回は多すぎます。真になるのは i ＝ 1 の 2 回、i ＝ 3 と i ＝ 6 の 3 回ずつで計 8 回です。

仕組み

この探し方は、先頭位置を 1 つずつずらしながら、そのつど key と頭から比べる素朴な文字列検索です。違う文字に当たった時点でその位置を打ち切るので、比較の回数は data の中身で変わります。

回数を問う問題は、i ごとに比較した結果を表に書いて数えると確実です。「真になった回数」と「見つかった数」を取り違えないように、何を数えるのかを先に確かめます。

この問に出る言葉