基本情報技術者過去問題 平成27年秋期 午後問8

問8 

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

〔プログラムの説明〕
 関数 BMMatch は,Boyer-Moor-Horspool法(以下,BM法という)を用いて,文字列検索を行うプログラムである。BM法は,検索文字列の末尾の文字から先頭に向かって,検索対象の文字列(以下,対象文字列)と1文字ずつ順に比較していくことで照合を行う。比較した文字が一致せず,照合が失敗した際には,検索文字列中の文字の情報を利用して,次に照合を開始する対象文字列の位置を決定する。このようにして明らかに不一致となる照合を省き,高速に検索できる特徴がある。
  • 対象文字列をText[ ],検索文字列をPat[ ]とする。ここで,配列の添字は1から始まり,文字列Text[ ]のi番目の文字はText[i]と表記される。Pat[ ]についても同様にi番目の文字はPat[i]と表記される。また,対象文字列と検索文字列は,英大文字から構成される。
     例えば,対象文字列Text[ ]が"ACBBMACABABC",検索文字列Pat[ ]が"ACAB"の場合の例を図1に示す。
  • 関数 BMMatch では,照合が失敗すると,次に照合を開始する位置まで検索文字列を移動するが,その移動量を格納した要素数26の配列Skip[ ]をあらかじめ作成しておく。Skip[1]に文字"A"に対応する移動量を,Skip[2]に文字"B"に対応する移動量を格納する。このように,Skip[1]〜Skip[26]に文字"A"〜"Z"に対応する移動量を格納する。ここで,検索文字列の長さをPatLenとすると,移動量は次のようになる。
    1. 検索文字列の末尾の文字Pat[PatLen]にだけ現れる文字と,検索文字列に現れない文字に対応する移動量は,PatLenである。
    2. 検索文字列のPat[1]からPat[PatLen-1]に現れる文字に対応する移動量は,その文字が,検索文字列の末尾から何文字目に現れるかを数えた文字数から1を引いた値とする。ただし,複数回現れる場合は,最も末尾に近い文字に対応する移動量とする。
  • 図1で示したPat[ ]の例の場合,次の@〜Cに示すように,Skip[ ]は図2のとおりになる。
    1. 文字"A"は検索文字列の末尾から2文字目(Pat[3])と4文字目(Pat[1])に現れるので,末尾に近いPat[3]に対応する移動量の1(=2−1)となる。
    2. 文字"B"は検索文字列の末尾の文字にだけ現れるので,移動量はPatLen(=4)となる。
    3. 文字"C"は検索文字列の末尾から3文字目(Pat[2])に現れるので,移動量は2(=3−1)となる。
    4. "A","B"及び"C"以外の文字については検索文字列に現れないので,移動量はPatLen(=4)となる。
  • 図1の例で照合する場合の手順は,次の@〜Hとなり,その流れを図3に示す。この例では,PatLen=4なので,検索文字列の末尾の文字はPat[4]である。
    1. Text[4]とPat[4]を比較する。Text[4]とPat[4]は同じ文字"B"である。
    2. Text[3]とPat[3]を比較する。Text[3]の"B"とPat[3]の"A"は異なる文字である。
    3. @で検索文字列の末尾の文字Pat[4]と比較したText[4]を基準に,Text[4]の文字"B"に対応する移動量であるSkip[2]の値4だけPat[ ]を右側に移動し,Text[8]とPat[4]の比較に移る。
    4. Text[8]とPat[4]を比較する。Text[8]の"A"とPat[4]の"B"は異なる文字である。
    5. Cで検索文字列の末尾の文字Pat[4]と比較したText[8] を基準に,Text[8]の文字"A"に対応する移動量であるSkip[1]の値1だけPat[ ]を右側に移動し,Text[9]とPat[4]の比較に移る。
    6. Text[9]とPat[4]を比較する。Text[9]とPat[4]は同じ文字"B"である。
    7. Text[8]とPat[3]を比較する。Text[8]とPat[3]は同じ文字"A"である。
    8. Text[7]とPat[2]を比較する。Text[7]とPat[2]は同じ文字"C"である。
    9. 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 に関する解答群
  • 0
  • 1
  • I − PatLen
  • PatLen
  • PatLen − 1
  • PatLen − I

解答選択欄

  • a:
  • b:

解答

  • a=
  • b=

解説

この設問の解説はまだありません。

設問2

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

 図4のように,Text[ ] に"ABCXBBACABACADEC",TextLen に 16,Pat[ ] に"ABAC",PatLen に 4 を格納し,BMMatch(Text[ ],TextLen,Pat[ ],PatLen)を呼び出した。プログラムが終了するまでにαはc回実行され,βはd回実行される。またこの場合,関数 BMMatch の返却値はeである。
pm08_6.gif/image-size:430×130
c,d,e に関する解答群
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 12

解答選択欄

  • c:
  • d:
  • e:

解答

  • c=
  • d=
  • e=

解説

この設問の解説はまだありません。

設問3

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

  関数 BMMatch中のγの処理を
    I:PatLen − 1,I ≧ 1,−1
  に変更した場合,関数 BMMatchはf
f に関する解答群
  • 対象文字列中に,検索文字列が含まれていないのに,1以上の値を返す場合がある
  • 対象文字列中に,検索文字列が含まれているのに,−1を返す場合がある
  • 正しい値を返す

解答選択欄

  • f:

解答

  • f=

解説

この設問の解説はまだありません。
【27年秋期 午後問題】
 問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12 問13
© 2010-2019 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop