応用情報技術者過去問題 平成21年秋期 午後問2

問2 プログラミング

文字列照合処理に関する次の記述を読んで,設問1〜3に答えよ。

 ある文字列(テキスト)中で特定の文字列(パターン)が最初に一致する位置を求めることを文字列照合という。そのための方法として,次の二つを考える。ここで,テキストとパターンの長さは,どちらも1文字以上とする。

〔方法1 単純な照合方法〕
 テキストを先頭から1文字ずつパターンと比較して,不一致の文字が現れたら,比較するテキストの位置(比較位置)を1文字分進める。この方法による処理例を図1に示す。
pm02_1.gif/image-size:329×198
 この手順を基に,テキストとパターンを与えると,最初に一致した文字位置を返すアルゴリズムを作成した。このアルゴリズムを図2に示す。
 なお,テキストは配列 T,パターンは配列 P に格納されており,T[n] 及び P[n] はそれぞれのn番目の文字を,T.length 及び P.length はそれぞれの長さを示す。
pm02_2.gif/image-size:502×275
〔方法2 効率的な照合方法〕
 方法1では,パターンとテキストの文字が不一致となった場合,比較位置を1文字分進めている。ここでは,比較位置をなるべく多くの文字数分進めることで,照合における比較回数を減らすことを考える。
 パターンの末尾に対応する位置にあるテキストの文字(判定文字)に着目すると,次のように比較位置を進める文字数(スキップ数)が決定できる。
  • 判定文字がパターンに含まれていない場合は,判定文字とパターン内の文字の比較は常に不一致となるので,パターンの文字数分だけ比較位置を進める。また,判定文字がパターンの末尾だけに含まれている場合も,同様にパターンの文字数分だけ比較位置を進める。
  • 判定文字がパターンの末尾以外に含まれている場合は,判定文字と一致するパターン内の文字が,テキストの判定文字に対応する位置に来るように比較位置を進める。ただし,パターン内に判定文字と一致する文字が複数ある場合は,パターンの末尾から最も近く(ただし,末尾を除く)にある判定文字と一致するパターン内の文字が,判定文字に対応する位置に来るように比較位置を進める。

 この方法による処理例を図3に示す。
pm02_3.gif/image-size:502×193
 パターンが与えられると,判定文字に対応するスキップ数を一意に決定することができる。例えば,パターン HIJ に対して判定文字とスキップ数の対応表を作成すると表1のようになる。
pm02_4.gif/image-size:297×68
 この考え方を基に作成したアルゴリズムを図4に示す。
 なお,テキストは配列 T,パターンは配列 P,スキップ数を決める表の判定文字は配列 C,スキップ数は配列 D に格納されており,T[n],P[n],C[n],D[n] はそれぞれのn番目の文字又は数値を,T.length 及び P.length はテキストとパターンの長さを示す。
 このアルゴリズムは,三つの主要部分から成っている。一つ目は,与えられたパターンについて判定文字とスキップ数の対応表を作成する処理である。ここでは,配列 C に格納される空白文字は表1の"その他の文字"及びパターンの末尾の文字"J"を表現するために使用している。テキストとパターンは空白文字を含まないものとする。二つ目は,文字を比較する処理である。ここでは,現在の比較位置に対応したテキストとパターンを方法1と同様に1文字ずつ比較して,パターンに含まれる文字と対応するテキストの文字がすべて一致するか,不一致となる文字が見つかるまで繰り返す。三つ目は,判定文字とスキップ数の対応表を引いてスキップ数を決定する処理である。
pm02_5.gif/image-size:501×675

設問1

図2及び図4中のに入れる適切な字句を答えよ。

-解答入力欄-

  • ア:
  • イ:
  • ウ:

-解答例・解答の要点-

  • ア:T.length−P.Length+1
  • イ:P.Length
  • ウ:P.Length−j

-解説-

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

設問2

パターン HIPOPOTAMUS に対するスキップ数を表2に示す。に入れる適切な数値を答えよ。
pm02_6.gif/image-size:518×85

-解答入力欄-

  • エ:
  • オ:

-解答例・解答の要点-

  • エ:10
  • オ:6

-解説-

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

設問3

次のテキストとパターンに対して,図2でのαと図4でのβの実行回数をそれぞれ答えよ。

 テキスト:PICKLED_PEPPER
 パターン:PEP

-解答入力欄-

  • α:
  • β:

-解答例・解答の要点-

  • α:12
  • β:8

-解説-

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

Pagetop