Top　→ 応用情報技術者試験　→ 平成21年度秋期試験 午後問題　→　問2

水野のサイト

応用情報技術者試験

●平成21年度秋期試験 午後問題 問2
　「文字列照合処理」

【解説】
　文字列探索の、逐次探索法とボイヤー・ムーア法についての問題です。 この二つのアルゴリズムの考え方と、プログラム作成および実行効率評価の能力が問われています。

【設問1 解答】

ア	T.length - P.length + 1
イ	P.length
ウ	P.length - j

【設問1 解説】
　問題文の図1、2より、i はテキスト文字列Tの添え字であり、パターンPと照合する位置を示しています。 したがって、その最大値（ア）は T.length-P.length+1 となります。 iがこの値を超えると、Tの残りの文字はパターンPよりも短くなりますから、一致することはありえません。
　j はパターンPの添え字です。Pのすべての文字を対応する位置のTの文字と比較しています。 したがって、j は P の先頭から最後までを指しますので、（イ）は P.lengthとなります。
　 D[k]には、パターンPのj番目の文字に対するスキップ数を入れています。 スキップ数は、「判定文字と一致するパターン内の文字が、テキストの判定文字に対応する位置に来るように」決めます。 つまり、下図のように P.length−j となります。


【設問2 解答】

エ	10
オ	6

【設問2 解説】
　上記のように、パターンの j番目の文字に対するスキップ数は 「 Pの長さ−j 」です。 パターン「HIPOPOTAMUS」の長さは11、文字「H」はパターンの最初の文字ですから、 そのスキップ数は 11−1＝10 です。
　パターン内に同じ文字が複数ある場合は、「パターンの末尾から最も近く（ただし、末尾を除く）にある」文字をとります。 文字「P」は、パターンの3番目と5番目ですから、5番目の方で考えます。すなわち、11−5＝6 となります。

【設問3 解答】

α	12
β	8

【設問3 解説】
　αの位置では、最初にテキストの最初の3文字「PIC」とパターン「PEP」を比較します。 この場合、2文字目（αの2回目）の「I」⇔「E」で不一致となり、パターンを一文字分すすめます。 続く7回、つまりテキストの「ICKLED_」とパターンの比較は、パターンの最初の文字で不一致となりますから、 αは各々1回ずつ実行されます。 最後に、テキストの「PEP」とパターンの比較は、3文字とも一致しますから、αを3回実行し一致と判定します。 αは、合計12回実行されます。
　「効率的な照合方法」では、まずスキップ数を求めます。 「P」のスキップ数は2、「E」のスキップ数は1、その他の文字のスキップ数は「3」です。

---

このページの先頭