平成27年秋期午後問8 設問3
skpさん
(No.1)
https://www.fe-siken.com/kakomon/27_aki/pm08.html
関数 BMMatch中のγの処理を
I:PatLen - 1,I ≧ 1,-1
とすると、なぜ、検索文字列中に同じ文字が存在する場合に、先頭に近い文字の位置で当該文字に対応する移動量が上書きされるのでしょうか。
関数 BMMatch中のγの処理を
I:PatLen - 1,I ≧ 1,-1
とすると、なぜ、検索文字列中に同じ文字が存在する場合に、先頭に近い文字の位置で当該文字に対応する移動量が上書きされるのでしょうか。
2021.02.12 22:17
いいね正解大卒さん
★FE ブロンズマイスター
(No.2)
例として、問題中にあるPat[]の【ACAB】について考えてみましょう。
頭からSkip[]の値を設定した場合、Skip[1]の値がどうなるかをトレースします。
Skip[1]以外の値はひとまず置いておくので、I=1とI=3のときのみを考えます。
I=1のとき
Skip[Index(Pat[I])] = Skip[1]
PatLen - I = 4 - 1 = 3
なので
Skip[1] ← 3
I=3のとき
Skip[Index(Pat[I])] = Skip[1]
PatLen - I = 4 - 3 = 1
なのでSkip[1] ← 1
そして、この2つの処理はこの順番で行われます(Iを昇順に動かしているので)。
つまり、最終的なSkip[1]の値はI=3のときの処理で上書された結果1となります。
これが、Iを降順で動かした場合はどうなるでしょう。もうなんとなくお分かりかと思いますが、上記2処理が逆順で行われるため、最終的なSkip[1]の値はI=1のときの処理で上書された結果3となります。
つまり、本来移動量を1と設定すべきところに3と設定されてしまうわけです。
このケースでは検索文字列中に同じ文字Aが1文字目と3文字目で2回出てきます。1文字目で設定される移動量は3、3文字目で設定される移動量は1。後ろから設定し始めると先頭に近い1文字目の位置でAに対応する移動量が上書きされ、本来の移動量と齟齬が出る、これによってプログラムに不具合が出てくる、というわけです。
「検索文字列中に同じ文字が存在する場合に、先頭に近い文字の位置で当該文字に対応する移動量が上書きされます」というのは、そういうことです。
頭からSkip[]の値を設定した場合、Skip[1]の値がどうなるかをトレースします。
Skip[1]以外の値はひとまず置いておくので、I=1とI=3のときのみを考えます。
I=1のとき
Skip[Index(Pat[I])] = Skip[1]
PatLen - I = 4 - 1 = 3
なので
Skip[1] ← 3
I=3のとき
Skip[Index(Pat[I])] = Skip[1]
PatLen - I = 4 - 3 = 1
なのでSkip[1] ← 1
そして、この2つの処理はこの順番で行われます(Iを昇順に動かしているので)。
つまり、最終的なSkip[1]の値はI=3のときの処理で上書された結果1となります。
これが、Iを降順で動かした場合はどうなるでしょう。もうなんとなくお分かりかと思いますが、上記2処理が逆順で行われるため、最終的なSkip[1]の値はI=1のときの処理で上書された結果3となります。
つまり、本来移動量を1と設定すべきところに3と設定されてしまうわけです。
このケースでは検索文字列中に同じ文字Aが1文字目と3文字目で2回出てきます。1文字目で設定される移動量は3、3文字目で設定される移動量は1。後ろから設定し始めると先頭に近い1文字目の位置でAに対応する移動量が上書きされ、本来の移動量と齟齬が出る、これによってプログラムに不具合が出てくる、というわけです。
「検索文字列中に同じ文字が存在する場合に、先頭に近い文字の位置で当該文字に対応する移動量が上書きされます」というのは、そういうことです。
2021.02.13 01:16
skpさん
(No.3)
いいね正解大卒さん、丁寧な解説ありがとうございました。
トレースにおける上書きの理解不足でした。
トレースにおける上書きの理解不足でした。
2021.02.14 00:02
広告
返信投稿用フォーム
スパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。
広告