平成27年(H27)秋期 基本情報技術者試験 アルゴリズム問題 解き方解説

平成27年度秋期午後のアルゴリズム問題である問8の私の解き方・考え方について解説していきます。

問題

IPAの公式サイトで公開されています。このページでは問8についての解説を行います。

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2015h27_2/2015h27a_fe_pm_qs.pdf

問題の概要

今回の問題は文字列の検索に関するものです。[プログラムの説明]の(4)に絵付きでどのように検索するかの具体例が示されていますので、設問に入る前に[プログラムの説明]を一通り読み、[プログラムの説明]の(4)でプログラムの動きを確認して自分の理解を整理しておくと設問が解きやすいと思います。

スポンサーリンク

設問1

穴埋め問題ですね。[   a   ]と[   b   ]ともに[プログラムの説明]の(2)において説明されている移動量の設定部分の穴埋めになります。

まず①の通り移動量を設定するために、緑枠内で文字Iに対する移動量Skip[I]を全て検索文字列Pat[ ]の長さPatLenを格納しておきます。

次に②の通り移動量を設定するために、青枠内で検索文字列に出て来る文字Iに対する移動量Skip[I]を設定しています。

Pat[I]には検索文字列Pat[ ]の先頭からI文字目の文字が格納されていますので、末尾から何文字目であるかは、検索文字列Pat[ ]の長さPatLen+1からIを引けば算出可能です。さらに[プログラムの説明]の(2) – ②によれば、移動量Skip[I]はそこから1引いた数に設定する必要があるので、緑枠でPatLenに設定されたSkip[Index(Pat[I])]PatLen – Iで上書きしてやります。

これにより[プログラムの説明]の(2)で説明されている移動量の設定が完了します。

以上より、緑枠内の[   a   ]の答えはPatLenであり、青枠内の[   b   ]の答えはPatLen – Iとなります。

設問2

設問2は問題で示された入力データの時にプログラム中のαとβの部分が何回実行されるかと、BMMatchの返却値が問われている問題です。

実際に問題で示された入力データの時にプログラムがどのように動き、文字列の検索がどのように行われるかを見て行きましょう。

まず下記でSkip[ ]に移動量の格納が行われます。

Pat[ ]が図1と同じなのでSkip[ ]も図2と同じ結果が格納されます。また、上のプログラムの最後でPLastに検索文字列の長さPatLenが格納されます。

このPat[ ]やSkip[ ]に基づいて文字列の検索が行われます。検索を行なっているプログラムは下記になり、入力文字列の最後まで検索が終わるまで下記が繰り返し実行されます。

青枠内は検索位開始位置の設定を行なっている箇所です。

最初にここが実行される時(αが1回目)の検索位置の関係は下の図になります。

この状態から緑枠で対象文字列Text[ ]と検索文字列Pat[ ]が一致しているかどうかの確認を行います。

具体的には、対象文字列Text[ ]PText文字目から先頭方向に向かって検索文字列Pat[ ]と一致しているかどうかを一文字ずつ確認していきます。上の場合だと最初の比較で文字が異なるので文字列は一致していないと判断できます。

つまり、Text[PText] = Pat[PPat]が不成立です。ですのでβ部分は実行されず、次はオレンジ枠が実行されます。

オレンジ枠は次の対象文字列Text[ ]におけるの検索開始位置の計算が行われます。

プログラムの先頭部分で[プログラムの説明]の(2)に記載されているとおりに移動量がSkip[ ]に格納してありますので、ここでは単にそのSkip[ ]の値を足すことで次の検索開始位置を求めることができます。

続いて2回目のループ(αが2回目)が行われます。

青枠終了時の各変数は下の図のような関係になっています。

この状態から緑枠で一文字ずつ一致の確認が行われます。

一文字目はText[PText]Pat[PPat]の両方がCであり、Text[pText] = Pat[pPat]が成立します。この時初めてβ部分が実行されます。実行されますが、PPatは4なのでPPat=1は不成立となります。不成立の場合は次の文字が一致しているかを確認するためにPTextPPatそれぞれが1減らされます。

これをText[PText] = Pat[PPat]が不成立になる、もしくはText[PText] = Pat[PPat]が成立かつPPatが1になるまでループします。

今回はPPatが1の時にText[PText] = Pat[PPat]が不成立となりますので、3文字分βが実行されてループが終了し、オレンジ枠が実行されます。Text[PLast]はCなのでSkip[Index(C)]は4となり、PLastは12(8+4)となります。

続いて3回目のループ(αが3回目)が行われます。

青枠終了時の各変数は下の図のような関係になっています。

この状態から緑枠で一文字ずつ一致の確認が行われます。

今回は4文字分全てでText[PText] = Pat[PPat]が成立しますので、βは4回実行されることになります。さらにβ部分でPPat=1が成立しますので、現在のPTextの値である「9」を返却してBMMatch関数は終了します。

終了時点で、αは3回実行されていますので[   c   ]の答えは3です。

また、ループ2回目にβが3回、ループ3回目にβが4回実行されますので[   d   ]の答えは7です。

さらに、BMMatchの返却値はPTextの値である9になります。ですので[   e   ]の答えは9です。

設問3

γ部分を問題文の通りに変更した時にどのように動きが変わるかを問われている問題です。

実際に変更した場合にどのようにSkip[ ]が変わるかを見てみましょう。β部分を変更すると、[プログラムの説明]の(2) – ②で記載されている「ただし、複数回現れる場合は、最も末尾に近い文字に対応する移動量とする」が、「ただし、複数回現れる場合は、最も先頭に近い文字に対応する移動量とする」にアルゴリズムが変わってしまいます。

ですので図2で示されているSkip[ ]は下の図のように変わってしまいます。具体的にはSkip[Index(A)]の値が変わります。つまり、Skip[ ]に本来よりも大きい値が設定されることになります。

 

こうなった場合には、[プログラムの説明]の(4) – ⑤の動作が下記のように変わります。

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

Text[6]Text[9]Pat[ ]と一致するのに、その部分の検索が飛ばされるため、Text[ ]内にPat[ ]の文字列が存在するにもかかわらず、BMMatch関数は-1を返却されてしまっています。

γ部分の変更により移動量に本来よりも大きな値が設定されてしまうので、必要な部分の検索が飛ばされる可能性があり、検索文字列が対象文字列内に存在してもBMMatch関数がそれを見つけられなくなってしまっているのです。BMMatch関数は見つけられないと-1を返却します。ですので、   f   ]の答えは「対象文字列中に、検索文字列が含まれているのに、-1を返す場合がある」となります。

スポンサーリンク

解いてみた感想

個人的に一番難しかったのは[   b   ]ですね。末尾の文字を末尾から0文字目と考えてしまっていたので正解はPatLen – I – 1なのではないかと考えたのですが選択肢になくて止まってしまいました・・・。文字列に関する問題は文字数や何文字目かの部分で+1すれば良いのか-1すれば良いのかで迷ってしまうので苦手です・・・・。

 

本ページの図・プログラム・問題文について

図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。

出典:平成27年度 秋期 基本情報技術者試験(FE)試験区分 午後 問8

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です