基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成27年 秋期 基本情報技術者 午後 問08
問08   必須問題

 次のプログラムの説明及びプログラムを読んで,設問1〜3に答えよ。

 

〔プログラムの説明〕

 関数 BMMatch は,Boyer-Moore-Horspool 法(以下,BM 法という)を用いて, 文字列検索を行うプログラムである。BM 法は,検索文字列の末尾の文字から先頭に 向かって,検索対象の文字列(以下,対象文字列)と1文字ずつ順に比較していくことで照合を行う。 比較した文字が一致せず,照合が失敗した際には,検索文字列中の文字の情報を利用して, 次に照合を開始する対象文字列の位置を決定する。このようにして明らかに不一致となる照合を省き, 高速に検索できる特徴がある。

 

(1) 対象文字列を Text[],検索文字列を Pat[] とする。ここで,配列の添字は1から始まり, 文字列 Text[] の i 番目の文字は Text[i] と表記される。Pat[] についても同様に i 番目の 文字は Pat[i] と表記される。また,対象文字列と検索文字列は,英大文字から構成される。

 例えば,対象文字列 Text[] が“ACBBMACABABC”,検索文字列 Pat[] が“ACAB”の場合の例を図1に示す。


図1 対象文字列と検索文字列の格納例

 

(2) 関数 BMMatch では,照合が失敗すると,次に照合を開始する位置まで検索文字列を移動するが, その移動量を格納した要素数 26 の配列 Skip[] をあらかじめ作成しておく。 Skip[1] に文字“A”に対応する移動量を,Skip[2] に文字“B”に対応する移動量を格納する。 このように,Skip[1] 〜 Skip[26] に文字“A”〜“Z”に対応する移動量を格納する。 ここで,検索文字列の長さを PatLen とすると,移動量は次のようになる。

@ 検索文字列の末尾の文字 Pat[PatLen] にだけ現れる文字と,検索文字列に現れない文字に 対応する移動量は,PatLen である。

A 検索文字列の Pat[1] から Pat[PatLen−1] に現れる文字に対応する移動量は, その文字が,検索文字列の末尾から何文字目に現れるかを数えた文字数から1を引いた値とする。 ただし,複数回現れる場合は,最も末尾に近い文字に対応する移動量とする。

(3) 図1で示した Pat[] の例の場合,次の@〜Cに示すように,Skip[] は図2のとおりになる。

@ 文字“A”は検索文字列の末尾から2文字目(Pat[3])と4文字目(Pat[1]) に現れるので,末尾に近い Pat[3] に対応する移動量の1(=2−1)となる。

A 文字“B”は検索文字列の末尾の文字にだけ現れるので,移動量は PatLen(=4)となる。

B 文字“C”は検索文字列の末尾から3文字目(Pat[2])に現れるので,移動量は2(=3−1)となる。

C “A”,“B”及び“C”以外の文字については検索文字列に現れないので,移動量は PatLen(=4)となる。


図2 図1の格納例における Skip[] の値

(4) 図1の例で照合する場合の手順は,次の@〜Hとなり,その流れを図3に示す。 この例では,PatLen=4 なので,検索文字列の末尾の文字は Pat[4] である。


図3 図1の場合の照合手順

 

@ Text[4] と Pat[4] を比較する。Text[4] と Pat[4] は同じ文字“B”である。

A Text[3] と Pat[3] を比較する。Text[3] の“B”と Pat[3] の“A”は異なる文字である。

B @で検索文字列の末尾の文字 Pat[4] と比較した Text[4] を基準に, Text[4] の文字“B”に対応する移動量である Skip[2] の値4だけ Pat[] を右側に移動し, Text[8] と Pat[4] の比較に移る。

C Text[8] と Pat[4] を比較する。Text[8] の“A”と Pat[4] の“B”は異なる文字である。

D Cで検索文字列の末尾の文字 Pat[4] と比較した Text[8] を基準に,Text[8] の文字“A”に 対応する移動量である Skip[1] の値 1 だけ Pat[] を右側に移動し,Text[9] と Pat[4] の比較に移る。

E Text[9] と Pat[4] を比較する。Text[9] と Pat[4] は同じ文字“B”である。

F Text[8] と Pat[3] を比較する。Text[8] と Pat[3] は同じ文字“A”である。

G Text[7] と Pat[2] を比較する。Text[7] と Pat[2] は同じ文字“C”である。

H Text[6] と Pat[1] を比較する。Text[6] と Pat[1] は同じ文字“A”である。

 

 E〜Hの比較で,対象文字列 Text[] の連続した一部分が検索文字列 Pat[] に完全に一致したので, 検索は終了する。

〔関数 BMMatch の引数と返却値〕

 関数 BMMatch の引数と返却値の仕様は,次のとおりである。

 関数 BMMatch では,次の関数 Index を使用する。

 

〔関数 Index の仕様〕

 引数にアルファベット順で n 番目の英大文字を与えると,整数 n(1≦ n ≦ 26 )を返却値とする。

〔プログラム〕

設問1 プログラム中の に入れる正しい答えを,解答群の中から選べ。

a,b に関する解答群

ア Ø        イ 1        ウ I − PatLen       
エ PatLen        オ PatLen − 1        カ PatLen − I       
解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

設問2 次の記述中の に入れる正しい答えを,解答群の中から選べ。

 

 図4のように,Text[]に“ABCXBBACABACADEC”,TextLen に 16,Pat[] に “ABAC”, PatLen に 4 を格納し,BMMatch(Text[],TextLen,Pat[],PatLen)を呼び出した。 プログラムが終了するまでにα 回実行され, β 回実行される。 またこの場合,関数 BMMatch の返却値は である。

 


図4 対象文字列と検索文字列

c〜e に関する解答群

ア 3        イ 4        ウ 5        エ 6        オ 7       
カ 8        キ 9        ク 10        ケ 11        コ 12       
解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます

解答 e ←クリックすると正解が表示されます

設問3  次の記述中の に入れる正しい答えを,解答群の中から選べ。 ここで,プログラム中の には正しい答えが入っているものとする。

f に関する解答群

ア 対象文字列中に,検索文字列が含まれていないのに,1以上の値を返す場合がある

イ 対象文字列中に,検索文字列が含まれているのに,−1を返す場合がある

ウ 正しい値を返す

解答 f ←クリックすると正解が表示されます


[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]