令和7年度 科目B 問4
アルゴリズム
文字列照合に関する問題
次の記述中の［ ］に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は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
- イ2
- ウ3
- エ4
- オ5
- カ6
- キ7
- ク8
- ケ9
- コ10
答えと解説を見る
✓ これが正解ク8
解説
iごとに真の回数は2・0・3・0・0・3で、合計8回です。
関数searchは、dataの各位置iを先頭と仮定し、keyの1文字目から順に比べていく文字列照合です。βの行はdata[i ＋ j － 1]とkey[j]を比べる条件式で、一致すれば次の文字へ進み、一致しなければαの繰返し処理を終えて次のiへ移ります。軸は、一致が途中で途切れた場合でも、それまでに真になった回数は数えに入るという点です。
dataの要素数は8、keyの要素数は3なので、iは1から8 － 3 ＋ 1＝6まで動きます。i＝1では、aとa、bとbが一致して真が2回、3文字目のaとcが食い違って打ち切りです。i＝2はbとaが食い違い、真は0回です。i＝3では、a・b・cの3文字がすべて一致して真が3回となり、j＝3でresultに3を追加します。i＝4はbで始まり、i＝5はcで始まるので、どちらも1文字目で食い違い、真は0回です。i＝6では、末尾のa・b・cがすべて一致して真が3回となり、resultに6を追加します。
iごとの真の回数は2・0・3・0・0・3なので、合計は8回です。なお、βが評価された回数は全部で12回で、そのうち偽が4回です。
見分け方は、iごとに何文字目まで一致したかを表にして、途中で打ち切られた先頭の一致分も漏らさず足すことです。
ほかの選択肢はなぜ違うのか
- ア1：最初のi＝1だけでも、aとa、bとbの2回で条件式が真になっています。1回で済む数え方は、この呼出しのトレースのどこからも出てきません。
- イ2：2回は、keyと同じ並びが見つかった回数、つまりresultに追加される3と6の個数です。βの条件式は1文字ごとの比較なので、完全一致に至るまでの各文字の一致も1回ずつ数えます。
- ウ3：3回は、1文字目のaが一致するiの数（1・3・6）か、keyの要素数と同じ値です。1文字目の比較だけを数えると3になりますが、2文字目以降の比較が真になった分が抜けています。
- エ4：4回は、βの条件式が偽になった回数です。i＝1の3文字目、i＝2・4・5の1文字目の4か所で食い違いが起きますが、問われているのは真になった回数のほうです。
- オ5：5回は、iの範囲を8 － 3までで止め、最後のi＝6を回さなかった場合の値です（2＋0＋3＋0＋0）。上限はlenData － lenKey ＋ 1＝6なので、末尾の一致の3回も加わります。
- カ6：6回は、完全に一致したi＝3とi＝6の真だけを足した値です（3＋3）。i＝1では3文字目で打ち切られるものの、1文字目と2文字目の比較は真になっているので、その2回も数えます。
- キ7：iごとの真の回数2・0・3・0・0・3を、どこで区切ってどう組み合わせて足しても7にはなりません。この呼出しのトレースからは、7という値は導けません。
- ケ9：9回は、i＝1も3文字すべて一致したと数えた場合の値です（3＋3＋3）。i＝1の3文字目はdata[3]のaとkey[3]のcの比較で偽となり、そこで打ち切られます。
- コ10：βの評価は全部で12回、そのうち真が8回、偽が4回です。iごとの真の回数をどう足しても10にはならず、この呼出しのトレースからは導けません。
出典：令和7年度 基本情報技術者試験 科目B 問4
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）