応用情報技術者 試験情報＆徹底解説

https://www.ap-siken.com/kakomon/21_aki/pm02.html
この問題の問1ウについて質問があります。
表1のパターンHIJを元に図4の表の作成の部分をトレースしたところ、P.length-kでもP.length-jでも同じ結果になってしまったので、勘でP.length-kと回答し間違えてしまいました。

恐らくP.lengthがもっと長くなればP.length-kだと正しく動かなくなる部分が出てくるのだと思いますが、本番でそこまでトレースしてる時間はないと思います。

本番の試験でこの問題のように2パターンの回答が得られてしまった場合、どのように答えを絞り込めばよいのでしょうか。

この投稿は投稿者により削除されました。(2023.08.01 23:55)

この投稿は投稿者により削除されました。(2023.08.02 07:45)

> 表1のパターンHIJを元に図4の表の作成の部分をトレースしたところ、P.length-kでもP.length-jでも同じ結果になってしまったので、勘でP.length-kと回答し間違えてしまいました。

パターンがHIJの場合だとP.length - kでもP.length - jでも同じになると思います。

パターンHIJでトレースしたときに、

C[k]とP[j]が等しい  or C[k]と””が等しいのうち

C[k]と””が等しいのうちしかtrueにならなかったのではないでしょうか？

ではC[k]とP[j]が等しいとはどういう状況のときに使われるのかというと、

>判定文字がパターンの末尾以外に含まれている場合は，判定文字と一致するパターン内の文字が，テキストの判定文字に対応する位置に来るように比較位置を進める。ただし，パターン内に判定文字と一致する文字が複数ある場合は，パターンの末尾から最も近く(ただし，末尾を除く)にある判定文字と一致するパターン内の文字が，判定文字に対応する位置に来るように比較位置を進める。

のただし以降の末尾以外にパターンの判定文字と一致する文字列が複数ある場合だと考えられます。

P[]をHIIJとすると、この条件を満たしています。
この条件から自分で各文字のステップ数を求めると、H=3,I=1となります。

このときにトレースしてみると、Iのステップ数がP.length - jだと1、P.length - kだと2となり異なることが分かり、自分で計算したステップ数と一致する式P.length - jが答えだと分かります。

なるほど、確かにC[k]と""が等しいがtrueの場合しかif文の中は実行されないので、じゃあ前半分のC[k]とP[j]が等しいはなんのためにあるのかってなりますね。

とても分かりやすくて助かりました。
ありがとうございます。

私は，

> 〔方法2  効率的な照合方法〕
> 比較位置をなるべく多くの文字数分進めることで，
> 照合における比較回数を減らすことを考える。
> パターンの末尾位置にある文字(判定文字)に着目すると，
> 比較位置を進める文字数(スキップ数)が決定できる。

というアルゴリズムを過去に学習したことがあり，

HIPOPOTAMUS や PEP など，
パターン中に同じ文字が含まれている場合に
スキップ数配列の中身が単なる連番ではなくなる

という知識を持っていたので，

設問2のパターンが 図4のプログラムに与えられたならば
配列は次のようになるはずだということをイメージでき，

配列P[] = {"H", "I", "P", "O", "P", "O", "T", "A", "M", "U", "S" }
（この配列を指す添字は j ）（P.length は 11）

配列C[] = {"H", "I", "P", "O", "T", "A", "M", "U", "S" }
配列D[] = { 10,   9,   6,   5,   4,   3,   2,   1,  11 }
（この配列を指す添字は k ）

配列D[]の中身がこうなる計算式は P.length - j だと答えを出しました。

過去問題の学習を通じてアルゴリズムの要点についての知識を持っている者は
一つ一つ変化をトレースして正解を探しているわけではなく，
「この配列の中身はこうなるはずだから，計算式はこうならなきゃおかしい」
というアプローチで正解を求めているという例の紹介として書いてみました。

基本情報の科目Bの勉強でなんでもトレースする癖がついてました…
過去問題をひたすら解いて思考力をつけていきたいと思います。
ありがとうございます。

jjon-comさん

>HIPOPOTAMUS や PEP など，
パターン中に同じ文字が含まれている場合に
スキップ数配列の中身が単なる連番ではなくなる

前者の場合はその通りですがPEPは連番になると思います。

正確には「パターンの末尾を除いた文字列に同じ文字が含まれている場合にスキップ数配列の中身が単なる連番ではなくなる」となるのかなと。