HOME»基本情報技術者試験掲示板»平成27年秋期午後問8(アルゴリズムについて)
投稿する

平成27年秋期午後問8(アルゴリズムについて) [4646]

 THANHさん(No.1) 
https://www.fe-siken.com/kakomon/27_aki/pm08.html
理解力が乏しくて、質問させていただきます。
Text[] : A B C D C D E F と  Pat[] : C D C D の時、結果は正しくなくなると思います。
1回目のループでは4だけPat[]を右側に移動し、C D C D  は飛ばされてしまうことになるのではないでしょうか?
よろしくお願いいたします。
2022.11.20 04:32
jjon-comさん(No.2) 
FE ゴールドマイスター
> 関数 BMMatch では,照合が失敗すると,
> 次に照合を開始する位置まで検索文字列を移動するが,
> その移動量を格納した要素数26の配列Skip[ ]をあらかじめ作成しておく。

> ■I:1, I≦26, 1
> |・Skip[I]←PatLen【a】
> ■

の実行後に、移動量の配列は一時的に次のようになり、
Skip[] : 4 4 4 4 (以降省略)

> 〔関数 Index の仕様〕
> 引数にアルファベット順でn番目の英大文字を与えると,
> 整数n(1≦n≦26)を返却値とする。

> ■I:1, I≦PatLen-1, 1
> |・Skip[Index(Pat[I])]←PatLen-I【b】
> ■

の実行後に、移動量の配列は次のようになる。
Skip[] : 4 4 1 2 (以降省略)

----
質問者が例示した

 Pat[] : C D C D
Text[] : A B C D C D E F

において不一致は Pat[2]="D" において発生する。

> Skip[] : 4 4 1 2 (以降省略)
より、"D"に対応する移動量は2なので、

> 1回目のループでは4だけPat[]を右側に移動し、
というのは誤りです。
2022.11.20 12:51
返信投稿用フォームスパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。
© 2010- 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop