平成２７年度秋期午後のアルゴリズム問題である問８の私の解き方・考え方について解説していきます。
問題
IPAの公式サイトで公開されています。このページでは問８についての解説を行います。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2015h27_2/2015h27a_fe_pm_qs.pdf
問題の概要
今回の問題は文字列の検索に関するものです。[プログラムの説明]の(4)に絵付きでどのように検索するかの具体例が示されていますので、設問に入る前に[プログラムの説明]を一通り読み、[プログラムの説明]の(4)でプログラムの動きを確認して自分の理解を整理しておくと設問が解きやすいと思います。
スポンサーリンク
設問１
穴埋め問題ですね。[ a ]と[ b ]ともに[プログラムの説明]の(2)において説明されている移動量の設定部分の穴埋めになります。
まず①の通り移動量を設定するために、緑枠内で文字Iに対する移動量Skip[I]を全て検索文字列Pat[ ]の長さPatLenを格納しておきます。
次に②の通り移動量を設定するために、青枠内で検索文字列に出て来る文字Iに対する移動量Skip[I]を設定しています。
Pat[I]には検索文字列Pat[ ]の先頭からI文字目の文字が格納されていますので、末尾から何文字目であるかは、検索文字列Pat[ ]の長さPatLen+1からIを引けば算出可能です。さらに[プログラムの説明]の(2) – ②によれば、移動量Skip[I]はそこから１引いた数に設定する必要があるので、緑枠でPatLenに設定されたSkip[Index(Pat[I])]をPatLen – Iで上書きしてやります。
これにより[プログラムの説明]の(2)で説明されている移動量の設定が完了します。
以上より、緑枠内の[ a ]の答えはPatLenであり、青枠内の[ b ]の答えはPatLen – Iとなります。
設問２
設問２は問題で示された入力データの時にプログラム中のαとβの部分が何回実行されるかと、BMMatchの返却値が問われている問題です。
実際に問題で示された入力データの時にプログラムがどのように動き、文字列の検索がどのように行われるかを見て行きましょう。
まず下記でSkip[ ]に移動量の格納が行われます。
Pat[ ]が図1と同じなのでSkip[ ]も図2と同じ結果が格納されます。また、上のプログラムの最後でPLastに検索文字列の長さPatLenが格納されます。
このPat[ ]やSkip[ ]に基づいて文字列の検索が行われます。検索を行なっているプログラムは下記になり、入力文字列の最後まで検索が終わるまで下記が繰り返し実行されます。
青枠内は検索位開始位置の設定を行なっている箇所です。
最初にここが実行される時（αが１回目）の検索位置の関係は下の図になります。
この状態から緑枠で対象文字列Text[ ]と検索文字列Pat[ ]が一致しているかどうかの確認を行います。
具体的には、対象文字列Text[ ]のPText文字目から先頭方向に向かって検索文字列Pat[ ]と一致しているかどうかを一文字ずつ確認していきます。上の場合だと最初の比較で文字が異なるので文字列は一致していないと判断できます。
つまり、Text[PText] = Pat[PPat]が不成立です。ですのでβ部分は実行されず、次はオレンジ枠が実行されます。
オレンジ枠は次の対象文字列Text[ ]におけるの検索開始位置の計算が行われます。
プログラムの先頭部分で[プログラムの説明]の(2)に記載されているとおりに移動量がSkip[ ]に格納してありますので、ここでは単にそのSkip[ ]の値を足すことで次の検索開始位置を求めることができます。
続いて２回目のループ（αが２回目）が行われます。
青枠終了時の各変数は下の図のような関係になっています。
この状態から緑枠で一文字ずつ一致の確認が行われます。
一文字目はText[PText]とPat[PPat]の両方がCであり、Text[pText] = Pat[pPat]が成立します。この時初めてβ部分が実行されます。実行されますが、PPatは4なのでPPat=1は不成立となります。不成立の場合は次の文字が一致しているかを確認するためにPTextとPPatそれぞれが１減らされます。
これをText[PText] = Pat[PPat]が不成立になる、もしくはText[PText] = Pat[PPat]が成立かつPPatが1になるまでループします。
今回はPPatが1の時にText[PText] = Pat[PPat]が不成立となりますので、３文字分βが実行されてループが終了し、オレンジ枠が実行されます。Text[PLast]はCなのでSkip[Index(C)]は4となり、PLastは12(8+4)となります。
続いて３回目のループ（αが３回目）が行われます。
青枠終了時の各変数は下の図のような関係になっています。
この状態から緑枠で一文字ずつ一致の確認が行われます。
今回は4文字分全てでText[PText] = Pat[PPat]が成立しますので、βは４回実行されることになります。さらにβ部分でPPat=1が成立しますので、現在のPTextの値である「９」を返却してBMMatch関数は終了します。
終了時点で、αは３回実行されていますので[ c ]の答えは３です。
また、ループ２回目にβが３回、ループ３回目にβが４回実行されますので[ d ]の答えは７です。
さらに、BMMatchの返却値はPTextの値である9になります。ですので[ e ]の答えは９です。
設問３
γ部分を問題文の通りに変更した時にどのように動きが変わるかを問われている問題です。
実際に変更した場合にどのようにSkip[ ]が変わるかを見てみましょう。β部分を変更すると、[プログラムの説明]の(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 ]ですね。末尾の文字を末尾から０文字目と考えてしまっていたので正解はPatLen – I – 1なのではないかと考えたのですが選択肢になくて止まってしまいました・・・。文字列に関する問題は文字数や何文字目かの部分で+1すれば良いのか-1すれば良いのかで迷ってしまうので苦手です・・・・。
★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください！
基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ
本ページの図・プログラム・問題文について
図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。
出典：平成２７年度 秋期 基本情報技術者試験（FE）試験区分 午後 問８
アルゴリズム問題の対策（PR）
過去問を解いてみて感触はいかがだったでしょうか？
全く分からなかった...という方もいらっしゃるかもしれません。はっきりいってアルゴリズム問題は、特に慣れないと難易度は高いです。
なので、こういった方にはもっと "簡単なアルゴリズム問題を解いて慣れていく" ことをオススメします。で、この簡単なアルゴリズム問題を解くのにオススメの本が下記の うかる！ 基本情報技術者 [午後・アルゴリズム編] です。
オススメする理由は、特に本の前半部分で難易度の低いアルゴリズムの紹介や解説が行われているところです。こういったアルゴリズムの動作などを実際にトレースして追ってみたりすることで簡単な問題からアルゴリズム問題に慣れていくことができます。
また、「アルゴリズムとは？」といったアルゴリズム入門から解説してくれているので、プログラミングをやったことない方にも親切な内容になっています。
アルゴリズム問題に全く手がつかないというような方は、まずは上記のような本でアルゴリズムに慣れるのがオススメです。
慣れてきたら、あとは実際の過去問を解いて "さらに考える力を養う" ＆ "実際のアルゴリズム問題に慣れる" のが良いと思います。
私のサイトでも過去問の解説をしていますので是非参考にしてください。私の解説だけでなく、他の人の解説も参考にしたいような場合には、下記のような過去問の参考書もオススメです（アルゴリズム問題だけでなく、全問題の解説も充実しています）。
