総視聴再生時間43万分以上(2017年5月13日現在)の動画で基本情報技術者試験の過去問&キーワード解説!スキマ時間に動画!〜これじょIT〜

PR広告

平成27年度秋基本情報技術者試験 午後問8 データ構造及びアルゴリズム 設問2

TOP :

平成27年度秋基本情報技術者試験 午後問8 データ構造及びアルゴリズム

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

〔プログラムの説明〕

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

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

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

平成27年度秋応用情報技術者試験午後過去問8 データ構造及びアルゴリズム

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

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

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

(3) 図1で示したPat[ ]の例の場合、次の①~④に示すように、Skip[ ]は図2のとおりになる。

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

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

 ③ 文字"C"は検索文字列の末尾から3文字目(Pat[2])に現れるので、移動量は2(=3-1)となる。

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

平成27年度秋応用情報技術者試験午後過去問8 データ構造及びアルゴリズム

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

平成27年度秋応用情報技術者試験午後過去問8 データ構造及びアルゴリズム

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

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

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

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

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

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

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

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

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

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

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

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

平成27年度秋応用情報技術者試験午後過去問8 データ構造及びアルゴリズム

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

〔関数 Index の仕様〕

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

【プログラム】

○整数型関数: BMMatch(文字型: Text[], 整数型: TestLen, 文字型: Pat[], 整数型: PatLen)

○整数型: Skip[26], PText, PPat, PLast, I

■I: 1, I ≦ 26, 1
|・Skip[I] ← a
■
■I: 1, I ≦ PatLen - 1, 1 // ← γ
|・Skip[Index(Pat[I])] ← b
■
・PLast ← PatLen
■PLast ≦ TextLen
|・PText ← PLast // α
|・PPat ← PatLen
|■Text[PText] = Pat[PPat]
||▲PPat = 1 // β
|||・return (PText)
||▼
||・PText ← PText - 1
||・PPat ← PPat - 1
|■
|・PLast ← PLast + Skip[Index(Text[PLast])]
■
・return (-1)

設問2

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

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

平成27年度秋応用情報技術者試験午後過去問8 データ構造及びアルゴリズム

c、d、e に関する解答群

  • ア 3
  • イ 4
  • ウ 5
  • エ 6
  • オ 7
  • カ 8
  • キ 9
  • ク 10
  • ケ 11
  • コ 12

解説

前提条件

Text[]に"ABCXBBACABACADEC"

TextLen = 16

Pat[]に"ABAC"

PatLen = 4

ですのでSkipは下記の通りになります。この場合のSkipは4文字目Cからの移動量です。

Skip[1] = 1 // A

Skip[2] = 2 // B

Skip[3] = 4 // C

Skip[4] = 4 // D

...

Skip[24] = 4 // X

これがアルゴリズムの下記の部分に該当します。

■I: 1, I ≦ 26, 1
|・Skip[I] ← PatLen
■
■I: 1, I ≦ PatLen - 1, 1 // ← γ
|・Skip[Index(Pat[I])] ← PatLen - I
■

αは、移動が発生する直前に通るので、移動回数分実行されます。

βは、文字を比較し一致回する時に通るので、文字が一致した回数分実行されます。

ABCXBBACABACADEC

ABAC

この時点でαを通ります(αの合計は1)。

XとCは一致しませんので、移動します。

Textの「始めの」比較対象は"X"なので"4"移動します。

アルゴリズムは下記の通り(コメントに値を記載しています。)

・PLast ← PatLen // 4
■PLast /* = 4 */ ≦ TextLen /* = 16 */
|・PText /* = 4 */ ← PLast /* = 4 */ //-- α 通算1回目
|・PPat /* = 4 */ ← PatLen /* = 4 */
|■Text[PText] /* = "X" */ = Pat[PPat] /* = "C" */ //-- XとCは一致しません
||▲PPat = 1 // β //-- ここ以下は通らない
|||・return (PText)
||▼
||・PText ← PText - 1
||・PPat ← PPat - 1
|■
|/* PLast = 4 なので、Text[4]  */
|/* Text[4] = X なので、Index(X)  */
|/* Index(X) = 24 なので Skip[24]  */
|/* Skip[24] = 4 であり、PLast = 4 なので PLast = 8  */
|/* Textの「始めの」比較対象は"X"なので"4"移動します(次の検索対象は8)に。  */
|・PLast ← PLast + Skip[Index(Text[PLast])] 
■
・return (-1)

この時点でαは1回通過、βは0回通過

ABCXBBACABACADEC

++++ABAC

Patの位置がTextの最後尾を超えていないので比較が開始されます。

この時点でαを通ります(αの合計は2)。

CとCが一致するのでβを通ります(βの合計は1)。

AとAが一致するのでβを通ります(βの合計は2)。

BとBが一致するのでβを通ります(βの合計は3)。

BとAが一致しないので、移動します。

Textの「始めの」比較対象は"C"なので"4"移動します。

アルゴリズムは下記の通り

■PLast /* = 8 */ ≦ TextLen /* = 16 */
|・PText /* = 8 */ ← PLast /* = 8 */ //-- α 通算2回目
|・PPat /* = 4 */ ← PatLen /* = 4 */
|■Text[PText] /* = "C" */ = Pat[PPat] /* = "C" */ //-- CとCで一致
||▲PPat = 1 // β //-- β 通算1回目(PPat = 4なので returnには入らない)
|||・return (PText)
||▼
||・PText ← PText - 1 /* PText = 8 なので PText = 8 - 1 = 7 */
||・PPat ← PPat - 1 /* PPat = 4 なので PText = 4 - 1 = 3 */
|■ /* Text[PText] = Pat[PPat] に戻る(説明のためにアルゴリズムを書きます) */
|■Text[PText] /* = "A" */ = Pat[PPat] /* = "A" */ //-- AとAで一致
||▲PPat = 1 // β //-- β 通算2回目(PPat = 3なので returnには入らない)
|||・return (PText)
||▼
||・PText ← PText - 1 /* PText = 7 なので PText = 7 - 1 = 6 */
||・PPat ← PPat - 1 /* PPat = 3 なので PText = 3 - 1 = 2 */
|■ /* Text[PText] = Pat[PPat] に戻る(説明のためにアルゴリズムを書きます) */
|■Text[PText] /* = "B" */ = Pat[PPat] /* = "B" */ //-- BとBで一致
||▲PPat = 1 // β //-- β 通算3回目(PPat = 2なので returnには入らない)
|||・return (PText)
||▼
||・PText ← PText - 1 /* PText = 6 なので PText = 6 - 1 = 5 */
||・PPat ← PPat - 1 /* PPat = 2 なので PText = 2 - 1 = 1 */
|■ /* Text[PText] = Pat[PPat] に戻る(説明のためにアルゴリズムを書きます) */
|■Text[PText] /* = "B" */ = Pat[PPat] /* = "A" */ //-- BとAで一致しないので下記は通らない
||▲PPat = 1 // β 
|||・return (PText)
||▼
||・PText ← PText - 1 
||・PPat ← PPat - 1 
|■ 
|/* PLast = 8 なので、Text[8]  */
|/* Text[8] = C なので、Index(C)  */
|/* Index(C) = 3 なので Skip[4]  */
|/* Skip[4] = 4 であり、PLast = 8 なので PLast = 12  */
|/* Textの「始めの」比較対象は"C"なので"4"移動します(次の検索対象は12)。  */
|・PLast ← PLast + Skip[Index(Text[PLast])] 
■
・return (-1)

この時点でαは2回通過、βは3回通過

ABCXBBACABACADEC

++++++++ABAC

Patの位置がTextの最後尾を超えていないので比較が開始されます。

この時点でαを通ります(αの合計は3)。

CとCが一致するのでβを通ります(βの合計は4)。

AとAが一致するのでβを通ります(βの合計は5)。

BとBが一致するのでβを通ります(βの合計は6)。

AとAが一致するのでβを通ります(βの合計は7)。

すべて一致したので、この時のテキストの位置を返します。AはTextの9番目なので"9"を返します。

アルゴリズムは下記の通り

・PLast ← PatLen // 4
■PLast /* = 12 */ ≦ TextLen /* = 16 */
|・PText /* = 12 */ ← PLast /* = 12 */ //-- α 通算3回目
|・PPat /* = 4 */ ← PatLen /* = 4 */
|■Text[PText] /* = "C" */ = Pat[PPat] /* = "C" */ //-- CとCは一致
||▲PPat = 1 // β //-- β 通算4回目(PPat = 4なので returnには入らない)
|||・return (PText)
||▼
||・PText ← PText - 1 /* PText = 12 なので PText = 12 - 1 = 11 */
||・PPat ← PPat - 1 /* PPat = 4 なので PText = 4 - 1 = 3 */
|■ /* Text[PText] = Pat[PPat] に戻る(説明のためにアルゴリズムを書きます) */
|■Text[PText] /* = "A" */ = Pat[PPat] /* = "A" */ //-- AとAは一致
||▲PPat = 1 // β //-- β 通算5回目(PPat = 3なので returnには入らない)
|||・return (PText)
||▼
||・PText ← PText - 1 /* PText = 11 なので PText = 11 - 1 = 10 */
||・PPat ← PPat - 1 /* PPat = 3 なので PText = 3 - 1 = 2 */
|■ /* Text[PText] = Pat[PPat] に戻る(説明のためにアルゴリズムを書きます) */
|■Text[PText] /* = "B" */ = Pat[PPat] /* = "B" */ //-- BとBは一致
||▲PPat = 1 // β //-- β 通算6回目(PPat = 2なので returnには入らない)
|||・return (PText)
||▼
||・PText ← PText - 1 /* PText = 10 なので PText = 10 - 1 = 9 */
||・PPat ← PPat - 1 /* PPat = 2 なので PText = 2 - 1 = 1 */
|■ /* Text[PText] = Pat[PPat] に戻る(説明のためにアルゴリズムを書きます) */
|■Text[PText] /* = "A" */ = Pat[PPat] /* = "A" */ //-- AとAは一致
||▲PPat = 1 // β //-- β 通算7回目(PPat = 1なので returnには入る)
|||・return (PText) //-- PText = 9 なので 9を返す
||▼
||・PText ← PText - 1 /* returnで値を返しループを抜けるので通らない */
||・PPat ← PPat - 1 
|■ /* ループは抜けている */
|・PLast ← PLast + Skip[Index(Text[PLast])] 
■
・return (-1)

/* 終了 */

αは3回通過のでcには「ア 3」

βは7回通過のでdには「オ 7」

9を返すのでeには「キ 9」

が入ります!

平成27年度秋基本情報技術者試験 午後 問8 データ構造及びアルゴリズム 目次

平成27年度秋基本情報技術者試験 午後 目次

業務で書いたことがないプログラミング言語の解説は控えさせていただきますので、解説はありません。

TOP :

タグ: ,,,

PR広告

フェイスブックコメント

平成28年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成28年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成28年度春 基本情報技術者試験 午後 テキスト・動画解説

平成28年度春 基本情報技術者試験 午前 テキスト・動画解説

平成27年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午前 テキスト・動画解説

平成26年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成26年度春 基本情報技術者試験 午前 テキスト・動画解説