平成27年秋期試験午後問題　問8

午前試験免除制度対応！基本情報技術者試験のeラーニング【独習ゼミ】

問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に示す。
    pm08_1.png
  • 関数 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[ ]の例の場合，次の①～④に示すように，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)となる。
      pm08_2.png
  • 図1の例で照合する場合の手順は，次の①～⑨となり，その流れを図3に示す。この例では，PatLen＝4なので，検索文字列の末尾の文字はPat[4]である。
    pm08_3.png
    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. ④で検索文字列の末尾の文字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"である。
　⑥～⑨の比較で，対象文字列 Text[ ] の連続した一部分が検索文字列 Pat[ ] に完全に一致したので，検索は終了する。

〔関数 BMMatch の引数と返却値〕
　関数 BMMatch の引数と返却値の仕様は，次のとおりである。
pm08_4.png
　関数 BMMatch では，次の関数 Index を使用する。

〔関数 Index の仕様〕
　引数にアルファベット順でn番目の英大文字を与えると，整数n(1≦n≦26)を返却値とする。
pm08_5.png
広告

設問1

プログラム中の　に入れる正しい答えを，解答群の中から選べ。
a，b に関する解答群
  • 0
  • 1
  • I － PatLen
  • PatLen
  • PatLen － 1
  • PatLen － I
解答選択欄
  • a:
  • b:
  • a=エ
  • b=カ

解説

〔aについて〕
プログラム冒頭の2つのループ処理は、配列 Skip[] に"A"～"Z"に対応する移動量を格納する処理です。〔プログラムの説明〕では各文字に対応する移動量を次のように説明しています。
検索文字列の末尾の文字
検索文字列に現れない文字の移動量
PatLen
検索文字列の末尾以外に現れる文字
末尾から何文字目に現れるかを数えた文字数から1を引いた値
例）末尾から2文字目は1、末尾から3文字目は2
1回目のループ処理では Skip[] の全要素に[a]を格納しており、2回目のループ処理では検索文字列1文字目から末尾の1つ前までの文字を走査し、その文字に対応する Skip[] の要素を[b]で更新しています。[a]は、Skip[] の各要素の初期値となるものですので、"検索文字列の末尾の文字"および"検索文字列に現れない文字"の移動量である PatLen（検索文字列の長さ）が入ります。

∴a＝エ：PatLen

〔bについて〕
前述の通り、[b]を含む2回目のループでは検索文字列1文字目から末尾の1つ前までの各文字に対応する Skip[] の要素を更新しています。仮に Pat[] を本問の例の"ACAB"（PatLen=4）だとすると、Skip[] の要素には以下の値が入るのが適切です。
pm08_7.png
ループ変数 I は先頭から何文字目かを保持しているので、PatLen から I を引けば、末尾から何文字目に現れるか（末尾を0番目として何番目か）の値となります。

∴b＝カ：PatLen － I
広告

設問2

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

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

解説

〔c，d，eについて〕
Skip[] の作成後からプログラムの終了までをトレースしていきます。検索文字列は"ABAC"なので、Pat[] および Skip[] の内容は以下のようになっています。
pm08_8.png
PLast ← PatLen
PLast は4で初期化される
PLast(=4)≦TextLen(=16) が真でループ1回目
PText ← PLast、PPat ← PatLen
PText、PPatともに4が格納される（α）
Text[4](=X) = Pat[4](=C) が偽でループ終了
PLast ← PLast + Skip[Index(Text[PLast])]
Text[4] の値である"X"に対応する移動量を加算する
Skip[24] は4なので PLast ← 4 + 4 = 8
pm08_9.png
PLast(=8)≦TextLen(=16) が真でループ2回目
PText ← PLast、PPat ← PatLen
PText には8、PPat には4が格納される（α）
Text[8](=C) = Pat[4](=C) が真でループ継続
PPat(=4) が1ではないので分岐処理内は実行しない（β）
PText ← PText - 1、PPat ← PPat - 1
PText には7、PPat には3が格納される
Text[7](=A) = Pat[3](=A) が真でループ継続
PPat(=3) が1ではないので分岐処理内は実行しない（β）
PText ← PText - 1、PPat ← PPat - 1
PText には6、PPatには2が格納される
Text[6](=B) = Pat[2](=B) が真でループ継続
PPat(=2) が1ではないので分岐処理内は実行しない（β）
PText ← PText - 1、PPat ← PPat - 1
PText には5、PPatには1が格納される
Text[5](=B) = Pat[1](=A) が偽でループ終了
PLast ← PLast + Skip[Index(Text[PLast])]
Text[8]の値である"C"に対応する移動量を加算する
Skip[3] は4なので PLast ← 8 + 4 = 12
pm08_10.png
PLast(=12)≦TextLen(=16) が真でループ3周目
PText ← PLast、PPat ← PatLen
PText には12、PPat には4が格納される（α）
Text[12](=C) = Pat[4](=C) が真でループ継続
PPat(=4) が1ではないので分岐処理内は実行しない（β）
PText ← PText - 1、PPat ← PPat - 1
PText には11、PPat には3が格納される
Text[11](=A) = Pat[3](=A) が真でループ継続
PPat(=3) が1ではないので分岐処理内は実行しない（β）
PText ← PText - 1、PPat ← PPat - 1
PText には10、PPatには2が格納される
Text[10](=B) = Pat[2](=B) が真でループ継続
PPat(=2) が1ではないので分岐処理内は実行しない（β）
PText ← PText - 1、PPat ← PPat - 1
PText には9、PPatには1が格納される
Text[9](=A) = Pat[1](=A) が真でループ継続
PPat(=1) が1なので、分岐処理内を実行する（β）
return文で PText の値（=9）を返してプログラム終了
pm08_11.png
したがって、αの行は3回、βの行は7回実行され、プログラムの返却値は9になります。

∴c＝ア：3
　d＝オ：7
　e＝キ：9
広告

設問3

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

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

解説

γの処理で、Iを先頭から末尾の1つ前までではなく、末尾の1つ前から先頭までという順番に変えると、検索文字列中に同じ文字が存在する場合に、先頭に近い文字の位置で当該文字に対応する移動量が上書きされます。これにより、本来の移動量より大きな値が格納されることになります。

本来の移動量より大きく移動すると、一致する可能性のある部分を飛ばしてしまうことになり、対象文字列中に検索文字列が含まれているのにもかかわらず、見つからなかった場合の返却値である－1を返す不具合が生じます。

∴f＝イ：対象文字列中に，検索文字列が含まれているのに，－1を返す場合がある
広告
広告

前の問題次の問題

▲
Pagetop