- ベストアンサー
ボイヤ・ムーア法のアルゴリズムがよくわかりません
- ボイヤ・ムーア法のアルゴリズムについて理解が足りない
- テストでのパターンの移動の様子が正しく理解できていない
- どのような考え方をすればいいのか教えてほしい
- みんなの回答 (2)
- 専門家の回答
関連するQ&A
- ボイヤームーア法について
課題が分からなくて困っています。課題の内容は「ボイヤームーア法を用いてファイルの先頭からテキストを1行ずつ(1行の文字数は999文字以下とする)読み込み、何行目の何文字目に探索文字列の先頭が存在するか出力するプログラムを作成せよ。探索文字列中に同じ文字が含まれる場合については探索方法を改良せよ」というものです。1行の文字列を探索するプログラムは作れたのですが、複数の行を読み込んで何行目の何文字目かを出力させる方法がどうしてもわかりません。無知な私ですがどうかよろしくお願いします。締め切りは明日なのでなるべく早くお願いします。 #include<stdio.h> #include<string.h> #define MAX1 1000 #define MAX2 256 int bm(char txt[MAX1], char pat[MAX2]) { int a,b,len1,len2,skip[MAX2+1]; len1=strlen(txt); len2=strlen(pat); for(a=0;a<=MAX2;a++){ skip[a]=len2; } for(a=0;a<len2-1;a++){ skip[pat[a]] = len2-a-1; } while(a<len1){ b=len2-1; while(txt[a]==pat[b]){ if(b==0){ return(a); } b--; a--; } a+=skip[txt[a]]; } return(-1); } int main(void) { int x; char filename[MAX2],ex[MAX1],strg[MAX2]; FILE *fp; printf("Input filename:"); scanf("%s",filename); getchar(); fp=fopen(filename,"r"); if(fp == NULL){ printf("read open error!\n"); return(-1); } printf("Input search string:"); scanf("%s",strg); getchar(); for(i=0;i<MAX1;i++){ if(feof(fp)){ break; } fgets(ex[i],MAXCHR1,fp); } x=bm(ex,strg); if(x==-1){ printf("There is not pattern in the text"); } else{ printf("%s%d\n",strg,x+1); } fclose(fp); return 0; }
- ベストアンサー
- C・C++・C#
- ボイヤームーア法
今課題が分からなくて困ってます。ボイヤームーア法でテキストファイルから文字列を探索するプログラムなんですが以下のようなプログラムは作成できたのですがこれだとテキストの同じ行に同じ文字列がある場合、最初の1つしか表示してくれません。課題は今日提出なので早急にお願いします。 例 テキストabcabcabc 文字列abc 結果abc line1 rank1 どうすれば全部表示させられるのか教えてください。 #include<stdio.h> #include<string.h> #define MAXCHR1 1000 #define MAXCHR2 256 int bm(char txt[MAXCHR1], char pat[MAXCHR2]) { int a,b,length1,length2,skip[MAXCHR2+1]; length1=strlen(txt); length2=strlen(pat); for(a=0;a<=MAXCHR2;a++){ skip[a] = length2; } for(a=0;a<length2 - 1;a++){ skip[pat[a]] = length2 - a - 1; } while(a<length1){ b=length2 - 1; while(txt[a] == pat[b]){ if(b==0){ return(a); } b--; a--; } a += skip[txt[a]]; } return(-1); } int main(void) { int x,line=0; char filename[MAXCHR2],ex[MAXCHR1][MAXCHR1],strg[MAXCHR2]; FILE *fp; printf("Input filename:"); scanf("%s",filename); getchar(); fp=fopen(filename,"r"); if(fp == NULL){ printf("read open error!\n"); return(-1); } printf("Input search string:"); scanf("%s",strg); getchar(); while(fgets(ex,MAXCHR1,fp)!=NULL){ x=bm(ex,strg); ++line; if(x==-1){ printf("There is not '%s' in %dth line\n",strg,line); } else{ printf("%s line%d rank%d\n",strg,line,x+1); } } fclose(fp); return 0; }
- 締切済み
- C・C++・C#
- BM法(ボイヤームーア法)について
BM法(ボイヤームーア法)について VisualC++にて、BM法のプログラムを作りたいと思いましたが、書き方が、わかりません。 概要を下記にまとめますので、どなたか、作ってみてくれませんか? お早めにお願いします!! 1.scanf(入力関数(これ以外でも可))にて、テキスト(検索される文字列)を入力する。 2.上記にて、パターン(比較する文字列)を入力する。 3.BM法にて、1.と2.を比べて、あったら、"○○文字目にありました。\n\n" 4.続けて検索するか、しないか(While(これ以外でも可))を入力してもらう。(C(大文字か、小文字のC)を入力したら、続ける。E(大文字か、小文字のE)を入力したら、終了する))) 上記のような、プログラム作りは可能でしょうか? 可能なら、作ってみてくれませんか? 不可能なら、どこがダメか、どうしたらよいか、を踏まえ、サンプル的なプログラムを作ってみてくれませんか? お願いします。
- ベストアンサー
- C・C++・C#
- アルゴリズムの学習法について
当方、全くの素人ですが、情報処理技術者の資格を受験したいです。 アルゴリズムの問題に行き詰まっているのですが、アルゴリズムはどのように学習したらよろしいのでしょうか? よろしくお願いします。
- ベストアンサー
- 情報処理技術者
- アルゴリズム攻略法
こんにちは。 19日に基本情報を受験予定です。午後対策でゆきずまり、投稿させていただきます。 大滝みやこ先生の「アルゴリズム解法」をひととおり学習しました。 最初は頭が痛く、同じaという変数が、あるときは要素番号を示す添え字であったり「カウンタ」であったり、文脈から判断するのは短時間では無理だという思いを抱き、さじを投げましたが、学習過程で思考力の訓練になっていることを実感し、正直はまりかけています。 ただ、試験では、設問の条項と、擬似言語の記述を直感的に結びつけ、選択肢を空欄にあてはめて全体理解を深めてゆく、というのがポイントのようにも思いました。つまり、アルゴリズムは、「最初か理解を目指していたら時間が足りない」か、試験ではそこまでのレベルは求めていない、混沌とした記述から、必要な情報を拾い集め、設題に必要な回答をいかに早く判断できるか、というふうに思えました。 独学なので独りよがりの判断かもしれませんが、アルゴリズムについての考え方をお聞かせいただければと思います。 ちなみに、午前の模擬試験は、平均75%で「やや不安」なレベル。 とくに、情報とセキュリティがまったくりかいできていません」 「暗号化」だとか「ISO」だとか、、あのへんは暗記でしょうかね、、。
- ベストアンサー
- 情報処理技術者
- 引き放し法による除算アルゴリズムについて
突然の質問失礼いたします。 現在私は学校で引き戻し法・引き放し法といった除算のアルゴリズムについて学んでいるのですが、そのうちの引き放し法について質問したく投稿しました。 引き放し法について自分で勉強しようと思い、いろいろ調べていたのですが、商と余りを出す引き放し法は見つかっても、小数点以下にわたってまで商を求める引き放し法がまったく見つかりませんでした。 (例えば5÷2=2あまり1と結果を出すのではなく、5÷2=2.5と結果を出す引き放し法のことです。) 少数点以下にわたってまで商を求める引き放し法は商と余りを出す引き放し法で表現できるのでしょうか? もしよろしければ教えていただけると幸いです。また、参考にすべきインターネットサイト等もあれば教えていただけると助かります。
- ベストアンサー
- その他(プログラミング・開発)
- ゲイリー・ムーアを弾きたい!
ギターをやっていてゲイリー・ムーアをどうしても弾きたいのですが、教則本、又はビデオ、ついでにライブ・ビデオは出ていないのでしょうか?よろしくお願いします。
- 締切済み
- 海外アーティスト
お礼
とても詳しい回答ありがとうございます。 先生の言っていたことや教科書、また自分の考えていたやりかたとmtaka2さんのやりかたが 違いすぎて一体何が正しいのかよくわからなくなってしまいました。 mtaka2さんの回答を参考にしながらもっと調べてみようと思います。 ありがとうございました。