BohYoh.com《基本情報技術者試験》2007年度＝平成19年度・春期午前問13

基本情報技術者試験

2007年度＝平成19年度・春期

午前

問13

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

ア　0

イ　1

ウ　2

エ　4

解答

ウ

解説

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

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

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

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

　　　　　　ｉ　　　　　　　　　　　　　　　　　　　ｉ　　　　　　　　　　　　　　　　　①　２　３　４　５　６　７　　　　　１　②　３　４　５　６　７　　　　　　┏━┯━┯━┯━┯━┯━┯━┓　　　┏━┯━┯━┯━┯━┯━┯━┓ 文字列Ａ　┃ａ│ａ│ｂ│ａ│ｂ│ｘ│△┃　　　┃ａ│ａ│ｂ│ａ│ｂ│ｘ│△┃ 　　　　　┗━┷━┷━┷━┷━┷━┷━┛　→　┗━┷━┷━┷━┷━┷━┷━┛ 　　　　　┏━┯━┯━┓　　　　　　　　　　　┏━┯━┯━┓　　　　　　文字列Ｂ　┃ａ│ｂ│△┃　　　　　　　　　　　┃ａ│ｂ│△┃　　　　　　　　　　　┗━┷━┷━┛　　　　　　　　　　　┗━┷━┷━┛　　　　　　　　　　　　①　２　３　　　　　　　　　　　　　１　②　３　　　　　　　　　　　　　ｊ　　　　　　　　　　　　　　　　　　　ｊ

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

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

　　　　　　　　ｉ　　　　　　　　　　　　　　　　　　　ｉ　　　　　　　　　　　　　　ｋ　　　ｉ　　　　　　　　　　　　　１　②　３　４　５　６　７　　　　　１　２　③　４　５　６　７　　　　１　２　３　④　５　６　７　　　　　　┏━┯━┯━┯━┯━┯━┯━┓　　　┏━┯━┯━┯━┯━┯━┯━┓　　┏━┯━┯━┯━┯━┯━┯━┓ 文字列Ａ　┃ａ│ａ│ｂ│ａ│ｂ│ｘ│△┃　　　┃ａ│ａ│ｂ│ａ│ｂ│ｘ│△┃　　┃ａ│ａ│ｂ│ａ│ｂ│ｘ│△┃ 　　　　　┗━┷━┷━┷━┷━┷━┷━┛　→　┗━┷━┷━┷━┷━┷━┷━┛→　┗━┷━┷━┷━┷━┷━┷━┛ 　　　　　　　┏━┯━┯━┓　　　　　　　　　　　┏━┯━┯━┓　　　　　　　　　　┏━┯━┯━┓　　　　　　文字列Ｂ　　　┃ａ│ｂ│△┃　　　　　　　　　　　┃ａ│ｂ│△┃　　　　　　　　　　┃ａ│ｂ│△┃　　　　　　　　　　　　　┗━┷━┷━┛　　　　　　　　　　　┗━┷━┷━┛　　　　　　　　　　┗━┷━┷━┛　　　　　　　　　　　　　　①　２　３　　　　　　　　　　　　　１　②　３　　　　　　　　　　　　１　２　③　　　　　　　　　　　　　　　ｊ　　　　　　　　　　　　　　　　　　　ｊ　　　　　　　　　　　　　　　　　　ｊ

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

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