- ベストアンサー
BMサーチというアルゴリズム
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
Googleで検索すると以下のようなサイトに解説がありました。 ボイヤー-ムーア文字列検索アルゴリズム http://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%A4%E3%83%BC-%E3%83%A0%E3%83%BC%E3%82%A2%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0 ９．Boyer-Mooreの検索法 http://itpro.nikkeibp.co.jp/article/COLUMN/20061024/251654/?ST=develop&P=9 検索アルゴリズム http://www2.starcat.ne.jp/~fussy/algo/algo7-4.htm 中々ユニークな検索法ですね。 多分、標準のCライブラリはこのような事はしていないと思います。
その他の回答 (2)
- επιστημη（@episteme）
- ベストアンサー率46% (546/1184)
BM法は検索文字列が長くないとさほどに速くありません。 Cライブラリでの文字列検索はその多くが: 検索文字列の最初の1文字を探し、そこから続く文字列が検索文字列と一致するかを調べています。 いまどきのメモリもCPUも高速なのでよほど効率の悪いアルゴリズムでない限りさほどの差はありませんけどね。
- asuncion
- ベストアンサー率33% (2126/6287)
「BM法」で検索すると、多くのサイトがヒットします。 また、アルゴリズムに関する本を探して、 文字列探索に関する章があれば、 BM法について書いてあるかもしれません。書いてないかもしれません。
関連するQ&A
- データ構造とアルゴリズム
Ｃ言語の勉強をしているんですが最近はアルゴリズムについての勉強をしたくAmazon等で検索しています。 現在手持ちの本ではＣのプログラムの解説(書き方)が主でアルゴリズムについての解説がとてもすくないです。 やっぱりＣのソースがあったほうがいいのですが、詳しく解説(証明)している本が欲しいです。 お勧めの本がありましたら紹介してください。
- ベストアンサー
- C・C++・C#
- エクセルの関数の質問です
エクセルの関数の質問です 下記のＩＦ文ですがIF条件式が６件までしか設定できません。（それ以上は数式エラーです） エクセル自体に条件があるみたいですが、代用する計算式または回避する方法がございましたら ご教授願えるとありがたいです。 =IF(C9=$AA$59,$AB$59, IF(C9=$AA$60,$AB$60, IF(C9=$AA$61,$AB$61, IF(C9=$AA$62,$AB$62, IF(C9=$AA$63,$AB$63, IF(C9=$AA$64,$AB$64, IF(C9=$AA$65,$AB$65, IF(C9=$AA$66,$AB$66, ""))))))))
- ベストアンサー
- その他([技術者向] コンピューター)
- アルゴリズム・ネストループ方式って何？
プログラムの性能改善の課題が出ているのですが、アルゴリズムとしてネストループ方式、もしくはその延長上のものを用いること、とあります。 図書館でアルゴリズム関係の本を見てみたのですがどこにもネストループに関して説明がなく、大変困っています。 プログラム自体は、ファイルを読み込んで、表示させるだけの簡単なものです。 簡単に抜き出すと、 for (i=0;; i++){ if ((st = read_a(fd_name, &name_buf, i)) <=0) break; for (j = 0;; j++){ if ((st =read_a (fd_home,&home_buf ,j)) <= 0) break; if (!strcmp(name_buf.a , home_buf.b)){ printf("%s =%s (%s)\n", name_buf.a, name_buf.c , home_buf.c); } } if (st <0) break; といったものです。 注意事項として、break文を入れる手法を使わないこととあります。 お願いします。ネストループって何でしょう？教えてください。
- ベストアンサー
- C・C++・C#
- C言語のアルゴリズムについて
C言語で「標準入力から英語の文章を読み込んで，文字列Ilmorが出現した行をその行番号とともに表示するプログラムを作りなさい．」とプログラムを作りたいのですが、文字列を発見するところまでは分かるのですが、その行どうやって表示すればいいのか分かりません。また、文章を読み込むのもすごくややこしく最後にエンターを二回押すなどの制限があります。(scanf) 参考になるプログラムを書いていただける方いませんか？できればC言語のアルゴリズムについて詳しく書いた本やサイトがあれば教えていただきたいです。 レベルは超入門的な本を２，３冊読んだ程度です。アルゴリズムなどにはまったく触れてなかったし、ライブラリー関数も少ししか載ってなかったので関数の本もあれば教えていただきたいです。
- ベストアンサー
- C・C++・C#
- アルゴリズム(2分探索木)の問題について
２分探索木のアルゴリズムに関する問題について質問させていただきます。 [問題] 集合Sに対する2文探索木とは、ラベルつきの2分木で、 その頂点vにはSのある要素l(v)がラベルとしてつけられている。 l(v)は次の性質を満たす。 １．vの左部分木の頂点uに対して l(u) < l(v) 2．vの右部分木の頂点uに対して l(u) > l(v) 3．Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。 図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。 いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、 そうでなければ"いいえ"を出力するアルゴリズムを考える。 このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。 ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。 含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。 ・アルゴリズム procedure SEARCH(a,v): if a = l(v) then return "はい" else if a < l(v) then if vが左の子wを持つ then return SEARCH( ア ) else return "いいえ" else イ 以下の問題に答えよ。 (1) 上のアルゴリズムのア,イを埋めよ。 (2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。 削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。 (i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある 以上です。 設問(1)は解けました。 答えは ア: a,w イ: a > l(v) then if vが右の子wを持つ then return SEARCH(a,w) else return "いいえ" になるのではないかと思います。 設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、 参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。 長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。
- ベストアンサー
- その他（プログラミング・開発）
- 二分探索アルゴリズムの終了条件について
いつもお世話になっています。 現在他人のプログラムを読解する力をつけようと 訓練しています。 以下の文はとあるアルゴリズム本の２分探索の個所を 抜粋したものです。 int bs(*array, size, mokuteki) { ue=size-1, sita=0; while(1){ naka=(sita+ue) / 2; if(array[naka] == mokuteki) return ARU; else if(sita > ue) //・・・・・・★ return NAI; else { if(array[naka] < mokuteki) sita = naka+1; else ue = naka-1; } } } ここで★部分の終了条件なのですが、なぜ sita >= ue でいけないのか自分では理解できません。 要はsitaとueが同じ値になり、目的値が見つからなかった のに再度ループする必要があるのか？、ということです。 特に明確な答えはいりませんがぜひ ご意見を聞かせてください。 ちなみに作者は 「ue==sitaの状態ならば、幅１の範囲がありますから ループをもう一回実行する必要があります。」 と書いています。私には理解できません。 ちなみにこの本は「Javaで学ぶアルゴリズムとデータ構造」 という本です。だいたい一通り読みましたが読んでて 楽しいしわかりやすいし良書だと思います。高価ですが・・・。
- ベストアンサー
- その他（プログラミング・開発）
- プログラミングについての質問です。
プログラミングについての質問です。 できるだけ早めの解答をお待ちしてます。 次の構文をC言語として表したいのですが、一応作っては見たもののできません。 1.S→E<A4> 2.E→TX 3.X→＋<A1>T<A2>X 4.X→ε 5.T→FY 6.Y→*<A1>F<A2>Y 7.Y→ε 8.F→-<A1>F<A2>Y 9.F→I<A1> 10.F→(E) 11.I→a|b|c|d|e A1はスタック上に項目を挿入するという動作。 A2はスタックから３つの項目を除去し、それらを'='と次に割り当てられる４つ組とともに印刷し、この整数をスタックにおくという動作。 A3はスタックから２つの項目を除去し、それらを'='と次に割り当てられる４つ組とともに印刷し、この整数をスタックにおくという動作。 A4はスタックから１つの項目を除去する。 #include<stdio.h> #include<string.h> intmain(void) { charsymbol[10][10]; inti=0,j,k=0; printf("Inputsymbol:"); while(1) {scanf("%s",symbol[i]); if(strcmp(symbol[i],"_")==0) {i--;break;} i++;} printf("symbol="); for(j=0;j<=i;j++) {printf("%s",symbol[j]);} printf("¥n"); gotoS; S: if(strcmp(symbol[k],"a"|"b"|"c"|"d"|"e")==0) {gotoE;return;} elseif(strcmp(symbol[k],"-")==0) {gotoE;return;} elseif(strcmp(symbol[k],"(")==0) {gotoE;return;} else {gotoerror;} E: if(strcmp(symbol[k],"a"|"b"|"c"|"d"|"e")==0) {gotoT;gotoX;return;} elseif(strcmp(symbol[k],"-")==0) {gotoT;gotoX;return;} elseif(strcmp(symbol[k],"(")==0) {gotoT;gotoX;return;} else {gotoerror;} X: if(strcmp(symbol[k],"+")==0) {k++;gotoT;gotoX;return;} else {if(strcmp(symbol[k],"_")!=0) {gotoerror;} elseif(strcmp(symbol[k],")")!=0) {gotoerror;} } T: if(strcmp(symbol[k],"a"|"b"|"c"|"d"|"e")==0) {gotoF;gotoY;return;} elseif(strcmp(symbol[k],"-")==0) {gotoF;gotoY;return;} elseif(strcmp(symbol[k],"(")==0) {gotoF;gotoY;return;} else {gotoerror;} Y: if(strcmp(symbol[k],"*")==0) {k++;gotoF;gotoY;return;} elseif(strcmp(symbol[k],"_")==0) {gotoerror;} elseif(strcmp(symbol[k],")")==0) {gotoerror;} elseif(strcmp(symbol[k],"+")==0) {gotoerror;} I: if(strcmp(symbol[k],"a"|"b"|"c"|"d"|"e")==0) {k++; } elsegotoerror; F: if(strcmp(symbol[k],"-")==0) {k++;gotoF; } else if(strcmp(symbol[k],"a"|"b"|"c"|"d"|"e")==0) {gotoI;} else {if(strcmp(symbol[k],"(")==0) {k++;gotoE; if(strcmp(symbol[k],")")!=0) gotoerror;} elsegotoerror;} error: printf("No¥n"); exit(1); 制限字数の関係でプログラムを削ったりしています。 見にくくてすみません。 御指導よろしくお願いします。
- 締切済み
- C・C++・C#
- strcmp( finddata.cFileName, "." )
http://www.ne.jp/asahi/oh/landd/prog_html/prog23.html 上記のサイトに strcat( dir_cpy, "\\*" ); search = FindFirstFile( dir_cpy, &finddata ); if( search != INVALID_HANDLE_VALUE ){ // 現在のディレクトリ（フォルダ）と親ディレクトリは排除 if( strcmp( finddata.cFileName, ".." ) != 0 && strcmp( finddata.cFileName, "." ) != 0 ){ ……… } while( FindNextFile( search, &finddata ) != 0 ){ このような意味のソースが有りますが、コメントの行位置では finddata.cFileName が "." 以外になったことがありません。 そのため、いつも if は偽で、 ……… の部分が実行されません。 どういう場合に ……… の部分の処理がされるんですか？
- ベストアンサー
- C・C++・C#
