基本情報技術者試験 2007年度 = 平成19年度・春期 午前 問13

 文字列Aが“aababx△”、文字列Bが“ab△”であるとき、流れ図の終了時点のk は幾らか。ここで、文字列の先頭の文字を1番目と数えるものとし、A[i ]はAのi 番目の文字を、B[j ]はBのj 番目の文字を、“△”は終端を示す文字を表す。

ア 0 イ 1 ウ 2 エ 4

解答



解説

 与えられたフローチャートは、文字列Aから文字列Bを力任せ法(単純法/素朴法=brute force method)によって探索するアルゴリズムです。
※文字列Aがテキストで、文字列Bがパターンです。

 各変数は、次の意味をもちます。
・変数i  … 文字列Aの走査用(着目文字の添字)。
・変数j  … 文字列Bの走査用(着目文字の添字)。
・変数k  … 探索成功時の文字列A側の添字(失敗時は0)。
・変数jmax  … 文字列Bの長さ(文字数)。

 フローチャートの流れを追っていきましょう。

■まず着目文字A[1]とB[1]とを比較します。これらの文字は一致しますので、i j の両方2に更新して次の文字に着目する準備をします。

      i                   i                  ① 2 3 4 5 6 7     1 ② 3 4 5 6 7       ┏━┯━┯━┯━┯━┯━┯━┓   ┏━┯━┯━┯━┯━┯━┯━┓ 文字列A ┃a│a│b│a│b│x│△┃   ┃a│a│b│a│b│x│△┃      ┗━┷━┷━┷━┷━┷━┷━┛ → ┗━┷━┷━┷━┷━┷━┷━┛      ┏━┯━┯━┓           ┏━┯━┯━┓       文字列B ┃a│b│△┃           ┃a│b│△┃            ┗━┷━┷━┛           ┗━┷━┷━┛             ① 2 3             1 ② 3              j                   j

 着目文字A[2]とB[2]は等しくありません。そこで、i を2に更新して、j を1に戻します。

■着目文字A[2]とB[1]とを比較します。これらの文字は一致しますので、i を3に、j を2に更新して次の文字に着目します。
着目文字A[3]とB[2]とを比較します。これらの文字は一致しますので、i を4に、j を3に更新して次の文字に着目します。

        i                   i                 i              1 ② 3 4 5 6 7     1 2 ③ 4 5 6 7    1 2 3 ④ 5 6 7       ┏━┯━┯━┯━┯━┯━┯━┓   ┏━┯━┯━┯━┯━┯━┯━┓  ┏━┯━┯━┯━┯━┯━┯━┓ 文字列A ┃a│a│b│a│b│x│△┃   ┃a│a│b│a│b│x│△┃  ┃a│a│b│a│b│x│△┃      ┗━┷━┷━┷━┷━┷━┷━┛ → ┗━┷━┷━┷━┷━┷━┷━┛→ ┗━┷━┷━┷━┷━┷━┷━┛        ┏━┯━┯━┓           ┏━┯━┯━┓          ┏━┯━┯━┓       文字列B   ┃a│b│△┃           ┃a│b│△┃          ┃a│b│△┃              ┗━┷━┷━┛           ┗━┷━┷━┛          ┗━┷━┷━┛               ① 2 3             1 ② 3            1 2 ③                j                   j                  j

 着目文字B[3]が文字列の終端を表す“△”であるため、変数k i jmax すなわち2を代入します。

※問題に示されているのは、探索に成功する例です。探索に失敗する場合は、B[j ]=“△”が成立しないため、変数kの値は0になります。

BohYoh.comトップページへ