- 締切済み
文字列の探索アルゴリズムについて
松井勝正といいます。自分なりのアイディアで文字列の探索アルゴリズム を作成したのですが。質問が2点程あります。 1点目：既に世に出回っているアルゴリズムかご教授願えれば幸いです。 2点目：改良の余地やバグ等ございましたらご指摘いただければ幸いです。 それではよろしくお願いいたします。
- mild7knight
- お礼率62% (5/8)
- その他(ソフトウェア)
- 回答数1
- ありがとう数2
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- kmee
- ベストアンサー率55% (1857/3366)
> 1点目：既に世に出回っているアルゴリズムかご教授願えれば幸いです。 「文字列探索」で検索すれば、沢山見つかるし、 ウィキペディアにも複数載ってるし http://ja.wikipedia.org/wiki/%E6%96%87%E5%AD%97%E5%88%97%E6%8E%A2%E7%B4%A2 ↑にある「外部リンク」にはJavaのサンプル付きで更に多くのアルゴリズムが紹介されている。 http://www-igm.univ-mlv.fr/~lecroq/string/ これくらいのことだったら、まずは人に聞く前に自分で調べましょうよ。 > 2点目：改良の余地やバグ等ございましたらご指摘いただければ幸いです。 ソースをざっと眺めただけでは、何をしようとしているかわかりませんでした。詳しく解析するつもりになれません。 どんなところが既存の方法より優れているか、説明できますか? mallocがやたらとあって、ポインタのポインタのポインタなんてものがあって.... と、下手すれば単純な探索より時間がかかりそうな気さえします。
関連するQ&A
- 文字列探索アルゴリズム(Aho Corasick法)をC言語で組みたい
はじめまして。 標題のとおり、 文字列探索アルゴリズム(Aho Corasick法)をC言語で組みたいと考えています。 簡単なコード例か、どこか情報元はありませんでしょうか？ 文字列「あかさたなはまやらわ」から キーワード「あか」・「たな」を探して 出力として、 「あか」…インデックス０ 「たな」…インデックス３ となるようなイメージのプログラミングです。 詳しい方がおりましたら、何卒ご教授お願い致します。
- ベストアンサー
- C・C++・C#
- アルゴリズムの問題－文字列探索
基本情報技術者の勉強をしているのですが、午後の問題のアルゴリズム(文字列探索)でつまっています。 どなたか、アドバイスいただけますでしょうか？ 以下、長くなってしまって申し訳ないです。 複数行の文字列からなるファイルの各行を、与えられた検索文字列で検索し、見つかった場合に、その行番号と開始位置を印字します。 例：検索文字列 YA ファイル内容 MINATOKU TORANOMON CHIYODAKU KASUMIGASEKI SHIBUYAKU SHIBUYA 印字結果 行番号-3 開始位置-6 行番号-3 開始位置-16 【宣言部は省略してあります】 ・ファイルを開く ・LN←0 ・R()←検索文字列 ・RN←文字数 ・レコード入力（ファイル,M(),sts） ■sts=0 │・MN←ファイルの文字列の文字列長 │・LN←LN+1 │・K←1 │■K<=MN-RN+1 ││・L←1 ││■M(K+L-1)=R(L)かつL<=RN │││・L←L+1 ││■ ││▲L>RN │││・LNとKを印字 ・・・・ここが分かりません ││▼ │■ │・レコード入力（ファイル,M(),sts） ■ ・ファイルを閉じる Kに数値を格納する記述が見当たりません。 Kをカウントアップするか、数値を代入する必要があると思うのですが、どうなのでしょうか？ ※問題の量が多いので、省略している部分もあります。質問内容が分からなかったら、補足要求してください。 よろしくお願いいたします。
- 締切済み
- 情報処理技術者
- ビットラインサーチ
以前、自分なりのアイディアでビットアレイサーチ(bitarraysearch)についても質問させて いただきましたが、今回も同様な質問をさせていただきたいと思います。 Webサイトをいろいろ検索した結果、今回作成したサーチアルゴリズムが無さそうだなとは 思うのですが、「もし既にあるよ」というお言葉があれば、回答をよろしくお願いします。 今回作成したサーチアルゴリズムは、ランダムに作成した5000000文字の中から任意の文字列の 位置を検索するというものです。任意の文字列は10000文字まで対応しています。もちろんこれらは ヘッダファイルの書き換えで変更することが出来ます。 最後にバグや改良点等ございましたら合わせてご回答頂ければ幸いです。
- 締切済み
- C・C++・C#
- 文字列の探索
ファイル名を指定して文字列の探索を行うというプログラムをＣ言語で作成したのですが、 コンパイルのときに警告で「問題のあるポインタの変換(関数 main )」と出て、うまい具合に動きません。改良点を教えてください。 #include<stdio.h> #include<string.h> #include<stdlib.h> unsigned char *s1; unsigned char *s2; unsigned char *cp; FILE *fp; char fname[64]; void TestStrStr(void); main(){ s1 = calloc(256, sizeof(unsigned char)); s2 = calloc(256, sizeof(unsigned char)); printf("Input Filename..."); scanf("%s",fname); while(1){ fp = fopen(fname, "r"); if(fp == NULL){ printf("ファイルを開くことができません...\n"); printf("Input Filename..."); scanf("%s",fname); }else break; } s1=fp; // printf("文字列1を入力してください："); // scanf("%s",s1); printf("文字列2を入力してください："); scanf("%s",s2); TestStrStr(); return 0; } void TestStrStr(void){ cp = strstr(s1, s2); if(cp == NULL) printf("'%s'に'%s'のいずれの文字も含まれない.\n", s1, s2); else printf("'%s'の中に現れる'%s'という文字列は%d文字目にある.\n", s1, s2, cp - s1 + 1); free(s1); free(s2); }
- ベストアンサー
- C・C++・C#
- テキストの中から与えられた文字を含む最短の文字列を求める為のアルゴリズムについて
例）Thatisanotebook. というテキストがあったとします。 与えられた文字がost(順番は構わない)だとすると、ostを含む最短の文字列はsanotです。 このときsanotと導くためのアルゴリズムが分かりません。 for文を使った簡単なものは作れるのですが、処理が遅すぎて困っています。 どなたかご教授お願いします。
- 締切済み
- C・C++・C#
- 経路探索
よろしくお願いします。 現在経路探索問題のプログラムを書いています。 そこでわからない点があったので教えてください。 以下のような(n行,m列)の経路があります。 (0,0)－(0,1)－(0,2)－(0,3) (1,0)－(1,1)－(1,2)－(1,3) (2,0)－(2,1)－(2,2)－(2,3) (3,0)－(3,1)－(3,2)－(3,3) (4,0)－(4,1)－(4,2)－(4,3) スタートを(4,3)としてゴール(0,0)にたどり着く全ての経路を求めたいです。 条件としてある点から 左(例えば(4,3)⇒(4,2)) 上(例えば(4,3)⇒(3,3)) 斜め(例えば(4,3)⇒(3,2)) にしか進むことはできません。 このような仕様のアルゴリズムはどのように書けばよいのでしょうか？？ ご解答要路しくお願いします。
- ベストアンサー
- C・C++・C#
- C#における改行を含む文字の探索
開発初心者です。 HTML上の改行を含む文字列をC#の 「 IndexOf 」 関数で探索するとき どのようにすれば良いのでしょうか？ IndexOf(<font size=\"-1\">\n) では成功しませんでした。 ご存知の方がいたら、ご教授ください。
- 締切済み
- その他（プログラミング・開発）
- Excelで各行の最小値となる列の探索
Excelで，各行ごとに，最小値を探索し，その最小値が どの列のデータかを計算したいのですが，どのようにすればよいのでしょうか？ 例えば 山田 鈴木 田中 データ(1) 10.3 0.42 0.5 データ(2) 1 10.1 4 データ(3) 5 11.8 2 といった感じのデータに対して， 山田 鈴木 田中 データ(1) 10.3 0.42 0.5 鈴木 データ(2) 1 10.1 4 山田 データ(3) 5 11.8 2 田中 という感じで，各列の1行目の値が出力されるように したいのですが。 一応，LookUp関数，Match＆Index関数を使ってみましたが，探索する文字列が小数のためか，探索できる行と N/Aになるものとが存在し，その差がなぜ生じるのかが わかりません。 上記関数にはこだわらないので，何か良い方法がありましたらご教授ください。
- ベストアンサー
- オフィス系ソフト
- 文字列を数値に高速変換
みなさんこんばんは。 文字列のセットがあります。 １．各文字列にインデックスを割り当てるには、 どのような方法がありますか？ 0 から N-1 まで。N は文字列の個数 ２．上記で作成したルールに基づき、 文字列をインデックスに高速に変換するには、 どのような方法がありますか？ 原理、アルゴリズム、ソースコード、 なんでも結構です。 よろしくお願いいたします。
- 締切済み
- C・C++・C#
- 文字列から文字列を検索するプログラム
現在、C言語を学習しています。 文字列から文字列を検索する関数に「strstr]がありますが、自作関数として自分で作成する方法を考えております。 文字列から文字を検索する事は出来たのですが、文字列を検索するシーケンスがわかりません。 有識者の方、御教授よろしく御願い致します。
- ベストアンサー
- C・C++・C#
お礼
早速のご回答ありがとうございます。こんなに早く回答を頂けるとはうれしい限りです。 自分で調べるという点につきましては、危言のお言葉有難く拝読させていただきました。 拙い文章ではございますが、ソースについて説明させていただきます。 まず、mallocやポインタのポインタを多用した件につきましては、ヒープ領域の確保という点からでございます。 次に、このアルゴリズムの特徴として申し上げたいのはint型32ビットのビット列を出来る限り有効利用したいという考えに基づいたものです。その為のアイディアとして、多重層のビット平面という考えに至りました。 この多重層のビット平面を簡単に説明いたします。通常ビット列は、インターネットや書籍などの説明にありますように横一直線に型宣言文だけビット長が図に示されているものを良く見かけます。 このビット列を縦にも拡張したらどうなるかと思い多重ポインタを利用し縦×横の平面を作成いたしました。つまり、縦軸が一文字分のデータ、横軸が文字数というものです。当然int型なので32ビット、つまり32文字しか扱えません、そこで多重層という考え方を取り入れ32文字以上の文字列も扱えるようにいたしました。 分かりにくい説明で誠に恐縮ではございますが、基本的な部分の説明とさせていただきます。長文大変失礼いたしました。
補足
さて、基本的な部分の説明をさせて頂きましたが、もう少し踏み込んだ説明をさせていただきます。縦軸の一文字分のデータの作成方法ですが、16で割った値と16で割った余りの値をそれぞれ用意します。少し説明が難しいのですが、多重ポインタの要素数16（一番右端）のポインタ配列部分に割った値と余りの値をそれぞれ格納します。これにより16×16=256（0xFF）のデータが作成されます。つまり一文字分のデータです。 ここで、2次元配列を思い描いてもらいたいのですが、 int bit[a][b]はa行b列の配列となります。これが3次元になっても4次元になっても列は必ず存在します。つまり一番右端の配列です。 先ほどのポインタ配列に話を戻しますが、一文字分のデータは一番右端のポインタ配列に格納されています。先ほど演算した値は、ポインタ配列の0～15のうちどこかに必ず格納されます。説明をさらに進めます。ソースを確認してもらえれば有難いのですが、bit[0][i][s－>indexbit][spot[0]]|=bitcalとbit[1][i][s－>indexbit][spot[1]]|=bitcalが記述されていると思いますが、この一番左端のポインタ配列の[0]と[1]に着目します。これが縦軸のビット列を表す重要な部分になります。省略して記述しますが、bit[0][][][spot[0]]が16で割った値の多重ポインタ配列、bit[1][][][spot[1]]が16で割った余りの値の多重ポインタ配列を表します。 つまり、一文字を縦軸のビット列に分解することにより横軸のビット列1ビット分で一文字を表現できるようにしたのです。 説明が長くなりましたので、ここで一旦切り上げさせていただきます。残りはまた次回説明させていただきたいと思います。長文大変失礼いたしました。