ボイヤ・ムーア法のアルゴリズムがよくわかりません。
テストで
kouhou-ni-jouhou-ga-aru.(-はスペースです。)
というテキストをjouhouで検索した場合のパターンの移動の様子をかけという問題で
先生の答えは
kouhou-ni-jouhou-ga-aru.
jouhou
-jouhou
-------jouhou
----------jouhou
となるらしいんですが、自分は
kouhou-ni-jouhou-ga-aru.
jouhou
---jouhou
---------jouhou
----------jouhou
だと思いました。
一行目のkouhouのuから比較してjで一致しなかったら
次は三文字目のuに合わせるのではないのでしょうか?
どういう考え方をすればいいのかをご教授いただきたいです。
よろしくお願いします。
No.2ベストアンサー
- 回答日時:
とりあえず、ちょっとだけ補足しておきます。
ます、Wikipedia のBM法の説明は理解できますでしょうか。
http://goo.gl/HJ8N
私の説明は、ほぼこれに沿ったものとして、テーブルの作り方を具体的に書き下したものとなっています。
結果だけ書くと、
★第一のテーブル
文字 シフト
u 0
o 1
h 2
j 5
他のあらゆる文字 6
★第二のテーブル
N パターン シフト
0 _____X 1
1 ____Xu 6
2 ___Xou 3
3 __Xhou 6
4 _Xuhou 6
5 Xouhou 6
となります。
No.1
- 回答日時:
どちらの回答も間違えてます。
まずはテーブルの算出について説明すると
★右から一文字目がいきなり不一致の場合についての、移動量テーブルの算出
a)不一致文字がoの場合
?????o
-jouho ○一致可能性あり
--jouh ×一致可能性なし
---jou ×一致可能性なし
----jo ○一致可能性あり
-----j ×一致可能性なし
→次は1文字ずらす
-jouhou
b)不一致文字がhの場合
?????h
-jouho ×一致可能性なし
--jouh ○一致可能性あり
---jou ×一致可能性なし
----jo ×一致可能性なし
-----j ×一致可能性なし
→次は2文字ずらす
--jouhou
c)不一致文字がjの場合
?????j
-jouho ×一致可能性なし
--jouh ×一致可能性なし
---jou ×一致可能性なし
----jo ×一致可能性なし
-----j ○一致可能性あり
→次は5文字ずらす
-----jouhou
d)不一致文字がそれ以外の時は6文字ずらす
★右から二文字以降で不一致の場合についての、移動量テーブルの算出
A)右から5文字目までは一致、6文字目で不一致の場合
Xouhou (Xはj以外)
-jouho ×一致可能性無し
--jouh ×一致可能性無し
---jou ×一致可能性無し
----jo ×一致可能性無し
-----j ×一致可能性無し
→次は6文字ずらす
------jouhou
B)右から4文字目までは一致、5文字目で不一致の場合
?Xuhou (Xはo以外)
-jouho ×一致可能性無し(質問者さんが挙げられた回答1つ目)
--jouh ×一致可能性無し
---jou ×一致可能性無し(質問者さんが挙げられた回答2つ目)
----jo ×一致可能性無し
-----j ×一致可能性無し
→次は6文字ずらす
------jouhou
C)右から3文字目までは一致、4文字目で不一致の場合
??Xhou (Xはu以外)
-jouho ×一致可能性無し
--jouh ×一致可能性無し
---jou ×一致可能性無し
----jo ×一致可能性無し
-----j ×一致可能性無し
→次は6文字ずらす
------jouhou
D)右から2文字目までは一致、3文字目で不一致の場合
???Xou (Xはh以外)
-jouho ×一致可能性無し
--jouh ×一致可能性無し
---jou ○一致可能性アリ
----jo ×一致可能性無し
-----j ×一致可能性無し
→次は3文字ずらす
---jouhou
E)右から1文字目までは一致、2文字目で不一致の場合
????Xu (Xはo以外)
-jouho ×一致可能性無し
--jouh ×一致可能性無し
---jou ×一致可能性無し
----jo ×一致可能性無し
-----j ×一致可能性無し
→次は6文字ずらす
------jouhou
となります。
このようなテーブルに基づいて処理しますから、検索実行の結果は、
kouhou-ni-jouhou-ga-aru.
jouhou →右から6文字目で不一致、パターンA、6文字ずらし
------jouhou →右から1文字目で不一致、パターンa、1文字ずらし
-------jouhou →右から3文字目で不一致、パターンD、3文字ずらし
----------jouhou →全文字一致
となります。
とても詳しい回答ありがとうございます。
先生の言っていたことや教科書、また自分の考えていたやりかたとmtaka2さんのやりかたが
違いすぎて一体何が正しいのかよくわからなくなってしまいました。
mtaka2さんの回答を参考にしながらもっと調べてみようと思います。
ありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
文字列にアルファベットが何文...
-
文字列検索機能
-
Accessのクエリで、replace関数...
-
vb.net IVSの漢字を1文字切り...
-
Excelのプルダウンで2列分の情...
-
Excel VBA 複数選択したリスト...
-
エクセルで、絶対値の平均を算...
-
Excelで指定した日付から過去の...
-
VB .netにて現在時刻+1時間後...
-
NTPサーバから時刻を取得する
-
特定のセルが空白だったら、そ...
-
VBAコマンドボタンを押すたびに...
-
ExcelのVBAで数字と文字列をマ...
-
マクロ 特定のセル値のみクリ...
-
VB DataRepeaterにて条件で表示
-
C言語のうるう年に関するプログ...
-
GASでスプレッドシートの一番上...
-
javaで週の最初の日(例:月曜日...
-
ExcelVBAを使って、値...
-
DataGridViewのセル編集完了後...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
Accessのクエリで、replace関数...
-
文字列の後ろから必要分だけ削...
-
ダブルクォーテーションを文字...
-
UNICODE文字が含まれているかの...
-
文字列にアルファベットが何文...
-
エクセル関数で記号から記号の...
-
C言語でギリシャ文字は使えます...
-
VBScriptでXcopyしたいのですが
-
vb.net IVSの漢字を1文字切り...
-
C言語について。
-
strcmp( )関数について教えて...
-
awk で右端の文字を1文字削除...
-
GetDlgItemTextについて
-
VS C++6.0のCString にて先頭1...
-
URLで使える文字・使えない...
-
CSVの禁則文字
-
文字数と単語数を数えるプログラム
-
右から何文字目にあるか文字位...
-
VB2008 文字列に等間隔にスペ...
-
◆COUNTIF関数またはダブルクォ...
おすすめ情報