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

PR広告

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

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)

設問3

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

  関数 BMMatch中のγの処理を

    I:PatLen - 1, I ≧ 1, -1

  に変更した場合、関数 BMMatchはf

f に関する解答群

  • ア 対象文字列中に、検索文字列が含まれていないのに、1以上の値を返す場合がある
  • イ 対象文字列中に、検索文字列が含まれているのに、-1を返す場合がある
  • ウ 正しい値を返す

解説

設問3のようにすると、下記のようにアルゴリズムが変わります。

■I: 1, I ≦ 26, 1
|・Skip[I] ← PatLen
■
■ I:PatLen - 1, I ≧ 1, -1 // ← I: 1, I ≦ PatLen - 1, 1 から変更
|・Skip[Index(Pat[I])] ← PatLen - I
■
・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)

図1

Text[] ACBBMACABABC

Pat[] ACAB

で見てみましょう

TextLen = 12

PatLen = 4

となります。

■I: 1, I ≦ 26, 1
|・Skip[I] ← PatLen /* = 4 */
■

Skipが初期化されます(今までと変わりません)

Skip[1] = 4

Skip[2] = 4

Skip[3] = 4

Skip[4] = 4

...

Skip[26] = 4

次のSkip生成が重要です。

■ I:PatLen - 1, I ≧ 1, -1 // ← I: 1, I ≦ PatLen - 1, 1 から変更
|・Skip[Index(Pat[I])] ← PatLen - I
■

PatLen = 4 なので 3, 2, 1とループします。

■ I:PatLen - 1, I ≧ 1, -1 // ← I: 1, I ≦ PatLen - 1, 1 から変更
|・Skip[Index(Pat[I])] ← PatLen - I
■
/* PatLen = 4 なので I = 3 */
/* Pat[3] = A */
/* Index(A) = 1 */
/* Skip[1] = 1 */

次のループ

■ I:PatLen - 1, I ≧ 1, -1 // ← I: 1, I ≦ PatLen - 1, 1 から変更
|・Skip[Index(Pat[I])] ← PatLen - I
■
/* I = 2 */
/* Pat[2] = C */
/* Index(C) = 2 */
/* Skip[3] = 2 */

次のループ

■ I:PatLen - 1, I ≧ 1, -1 // ← I: 1, I ≦ PatLen - 1, 1 から変更
|・Skip[Index(Pat[I])] ← PatLen - I
■
/* I = 1 */
/* Pat[3] = A */
/* Index(A) = 1 */
/* Skip[1] = 3 */

ループが終わります。

Skip[1] = 3 // A

Skip[2] = 4 // B

Skip[3] = 2 // C

Skip[4] = 4 // D

...

Skip[26] = 4 // Z

となります!

論理的に見ましょう

Text[] ACBBMACABABC

Pat[]

なので

Text[4] = B, Pat[4] = B は一致しています。

Text[3] = B, Pat[3] = A は一致していません。

Text[4] = Bなので、BのSkipだけ移動します。

Skip[2] = 4なので、4つ移動します。

ACBBMACABABC

++++ACAB

Text[8] = A, Pat[4] = B は一致しません。

Text[8] = Aなので、AのSkipだけ移動します。

Skip[1] = 3なので、3つ移動します。

ACBBMACABABC

+++++++ACAB

Text[11] = B, Pat[4] = B は一致します。

Text[10] = A, Pat[3] = A は一致します。

Text[9] = B, Pat[2] = C は一致します。

Text[11] = Bなので、BのSkipだけ移動します。

Skip[2] = 4なので、4つ移動します。

ACBBMACABABC

+++++++++++ACAB

ここで、検索文字列の最後(PLast)が検索対象の文字の長さ(TextLen)を超えるので、-1を返して終了します。

ACBBMACABABC

には、問題文の始めで解説されている通り、ACABを含みます。

ACBBM"ACAB"ABC

従って解答群の「イ 対象文字列中に、検索文字列が含まれているのに、-1を返す場合がある」に該当します。

fの答えは「「イ 対象文字列中に、検索文字列が含まれているのに、-1を返す場合がある」」です!

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

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

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

TOP :

タグ: ,,,

PR広告

フェイスブックコメント

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

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

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

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

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

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

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

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

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