問題
問4
次の記述中の□に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。
関数searchは、二つの文字型の配列を、それぞれ引数data及びkeyで受け取り、dataから、keyの要素の並びと同じ並びを全て探し、その先頭の要素番号を全て格納した配列を返す。見つからなければ、要素数0の配列を返す。
関数searchをsearch(｛”a”, “b”, “a”, “b”, “c”, “a”, “b”, “c”, “a”, “b”, “c”｝, ｛”a”, “b”, “c”｝)として呼び出すと、/*** β ***/の行の条件式が真となる回数は【 】回である。
- ア：1
- イ：2
- ウ：3
- エ：4
- オ：5
- カ：6
- キ：7
- ク：8
- ケ：9
- コ：10
[出典：基本情報技術者試験 令和7年度(科目B) 問4]
正解
正解は「ク」です。
解説
この問題は、文字列探索アルゴリズムの基本を理解しているかを問う問題です。
関数searchは、配列dataの中に配列keyの並びと一致する部分が何箇所あるかを調べます。問題文にある「/*** β ***/」の箇所では、配列dataの要素とkeyの要素が一致した場合に条件式が真になります。つまり、この条件式が「何回真になるか」は、「比較して一致した回数」を数えることと同じです。
具体例を考えます。配列dataは「a,b,a,b,c,a,b,c,a,b,c」、keyは「a,b,c」です。探索処理はdataの先頭からkeyと比較していき、部分一致した場合、その開始位置をresult配列に追加します。この際、探索は「一文字ずつずらしながら」部分一致を調べるため、同じ位置から始まる探索でも繰り返し一致判定が行われます。実際にプログラムの動作を追うと、部分一致を調べるためにdata[i+j-1]とkey[j]の比較が10回発生することが分かります（部分一致箇所が3回あることとは別の話です）。この比較は、data内で部分一致の探索が進むごとに必ず行われるため、比較回数は多くなります。
例えるなら、「教科書の文章から特定の単語を探す際に、1文字ずつ順番に読んでいき、一致したかどうか毎回確認する」作業をイメージすると分かりやすいです。したがって、最終的に条件式が真になる回数は「8回」となりますので、正解は「ク」です。
ア(1):
一致する回数は1回だけではありません。配列全体で複数回部分一致が発生します。
イ(2):
部分一致箇所は3か所存在し、それぞれの一致のたびに条件式は複数回成立するため誤りです。
ウ(3):
keyの長さと部分一致回数を混同している誤答です。
エ(4):
部分一致の個数と比較して一致した回数は異なるため誤りです。
オ(5):
一致回数を少なく見積もっている誤答です。
カ(6):
一部一致判定の回数だけでなく、探索の全範囲を考慮する必要があります。
キ(7):
惜しいですが、一致する回数は8回であり7回ではありません。
ケ(9):
条件式が真になる回数を多く見積もってしまっています。
コ(10):
全探索比較回数と一致回数を混同した過剰な回数となっています。
難易度
この問題の難易度は「普通」です。単なる一致回数ではなく「比較して一致した回数」を正確に数える必要があるため、配列探索や部分一致の仕組みを理解していないと間違えやすいです。探索処理の具体的な流れを追えるかが鍵となります。
用語補足
配列：
複数のデータを順番に格納するデータ構造です。例えば「a,b,c」のように並べて保持します。
部分一致検索：
配列の中で連続した要素が特定の並びと一致する箇所を探す処理です。文章から単語を探す作業に例えられます。
ループ処理：
同じ処理を何度も繰り返す命令です。プログラムでは配列の全要素を調べる際などに使用します。
解法のポイント
この問題のような部分一致探索アルゴリズムは、図を書いて目で追いながら理解することが効果的です。実際に手を動かしてインデックスを記録しながら、一致比較の回数や条件成立の場面を確かめる練習を行いましょう。
