- ベストアンサー
効率的な部分文字列一致検出アルゴリズムの実装方法
maru_yoshi_の回答
- maru_yoshi_
- ベストアンサー率39% (17/43)
> 実際の検索文字列には２バイト文字が含まれています。 > １バイト文字のみから構成される文字列と比べて性能が劣ることはありますか？ 確か文字列は unicode と書いておられたのでは？ 文字列比較が char 単位から TCHAR(wchar_t) 単位になるだけでありアルゴリズムによる性能の違いはありません。 問題はシフトJISによる文字列比較であり、２バイト文字の２バイト目の扱いです。 検索パターンの先頭文字がアスキーコードであったとき、被検索文字列中の２バイト文字の２バイト目が一致してしまうことがあります。これを避けるためには文字列比較を工夫する必要がありますが、 unicode であれば問題は無いはずです。 今回の課題は、複数（2～1000程度）のファイル名（約20文字）に対して部分文字列（4文字程度）が一致するかを判定したいとのことですが、実行時間を支配するのはファイル数であり、その計算量はファイル数の二乗に比例し、これを減らすことは困難です。まあ力技でやってもいいのではないかと思います。 プログラムの作成に時間をかけてもいいのであれば、私なら前述した「ラビン-カープ文字列検索アルゴリズム」を応用してみたいです。 まず、各ファイル名について部分文字列のハッシュ値群を作成する（手順１）。 次に、各ファイル名ペアについてハッシュ値群の比較を行い、一致するものがあった場合、そのハッシュ値の元となる部分文字列を比較する（手順２）。 という方法にします。手順１はファイル数に比例する処理時間であり、手順２はファイル数の二乗に比例する処理時間なので、手順２が単純な文字列比較を使用したものより高速ならばこの方法で高速化がはかれます。 手順１で作成するハッシュ値群をソートしておけば、手順２のハッシュ値群の比較では、ソート済の集合から一致するものを探す処理になり、計算量はO(n)になり、効率よく一致判定が可能になります。 ただし、この方法ではひとつひとつのハッシュ値に対して元の部分文字列（元の部分文字列へのリンク）を持っている必要があり、メモリが大量に必要になりそうです。
関連するQ&A
- java 文字列の部分一致について
/* 1から50まで順に数を表示する。 但し、その数が3の倍数か3の付く数字の場合、数字の後に！を表示する。 5 の倍数の場合は、数字の後に？と表示する。 両方の条件に合致した場合、数字の後に！？と表示する。 */ class Show{ public static void main(String[] args){ int i = 1; while(i <= 50){ if(i % 3 == 0 && i % 5 ==0){ System.out.println(i + "!?"); }else if(i % 5 == 0){ System.out.println(i + "?"); }else if(i % 3 == 0){ System.out.println(i + "!"); }else{ System.out.println(i); } i++; } } このような問題で、3を含む数字、とあるので、文字列の部分一致を検索する時に使用するStringクラスのindexOfを使用するのでは？と考えています。しかし、こちらはequalsで判定しますが、3の倍数は上記のコードにもある通り、==で判定しています。文字列判定と ==演算子は同じif(条件)の中には入れる事が出来ないので、じゃあどうする？という具合になってしまっています。どなたか「数が3の倍数か3の付く数字の場合」の処理を教えて頂けないでしょう？よろしくお願い致します。
- ベストアンサー
- Java
- ，で句切って部分一致をファイル出力
昨日も出したのですが自分で作成してみたんですけどヒントをいただいて作成してみたんですけど間をどうしていいかわからないので教えていただきたく載せました。 よろしくお願いいたします。 コメント部分をつくればいいみたいなのですが… (1)フォルダにファイルを用意する（CSV形式の文字列のファイル） (2)最初に文字列をキーボードから入力させる（文字列は半角で5文字まで、それ以外ならば繰り返し入力させる） (3)フォルダのファイル読み込み、(2)で入力した文字列が含まれている単語をファイルに出力（ファイルは新規作成 例： 読込み元ファイル： river,request,fire,maybe,best,over,coin,confortable, today,task,mary,face,popular,music,rock, mark,fight,replay,listen,pop, ------------------- 入力文字列：fi ファイル出力結果 fire, fight, ---------------------- 入力文字列：re ファイル出力結果 request, fire, replay public class Kadai4 { /** * @param args */ public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ String inputString; // ユーザーがキーボードから入力 // ファイルから1行読み込む String fileString =BufferedReader(FileReader); StringDetect sDetect = new StringDetect( );// ()の中に入れる new StringTokenizer( );// ()の中に入れる if(findMatch(nextToken)){ // ファイルに出す } } public class StringDetect{ private static String inputString = null // コンストラクタ public StringDetect(String str){ //ここに入れる } public static boolean findMatch(String word){ //wordとinputを比較して部分一致があれば //true、一致しなければfalseを返す } } }
- ベストアンサー
- Java
- 文字列比較
最長10文字の文字列を2件入力し、char型の配列にそれぞれ格納する。2つの文字列を比較し、文字列が同じだったら「equal」を表示し異なっていたら「Not equal」を表示するプログラムを作成せよという課題が出ました。 条件として、11文字以上の文字が入力されたら、先頭から10文字までを有効とし、11文字目以降を無視する。下記のプログラムで文字列1に11文字以上入力すると、うまく動きません。なぜ、うまくいかないかと、どうなおしたらよいかを教えてください。 #include<stdio.h> #include<string.h> #define max_length 10 void get_string (char *p_str, int size); int main() { char string1[max_length+2]; char string2[max_length+2]; printf("文字列1:"); get_string(string1,max_length+2); printf("文字列2:"); get_string(string2,max_length+2); if(!strncmp(string1,string2,max_length)) puts("equal"); else puts("Not equal"); } void get_string (char *p_str, int size) { fgets(p_str,size,stdin); }
- ベストアンサー
- C・C++・C#
- Javaの文字列の大小比較についてです。
Javaでは、文字列の大小比較をする時、StringのcompareToを使用しまが… compareToの中の処理は一旦char型に直して、それを比較しているのでしょうか? また、compareToを使用せずに、プログラム内に自分で書いた場合、処理速度は変化ありますか?
- ベストアンサー
- Java
- Excel 文字列 一致
２つの文字を比較して一致した文字の数を数える関数があれば教えてください。 例えばExcelでA1セルに「海山商事」A2セルに「海猫商事」を入れて比較し、一致している文字数（この場合は「3」）をA3に出力したいのですがどうしたらよいですか？大変恐縮ですがアドバイスください。よろしくお願いします。
- ベストアンサー
- オフィス系ソフト
- 文字列を抜き出してきてファイルを生成
当方はC++を用いております。文字列の部分列にアクセスして、 それを新たに文字列としたいのですが、可能でしょうか？ 具体的には、英数字、空白のみからなるレコードがあったとします。 例： 01 po 0979876 7行目から10行目までをとりだします。 0979 これをひとつの文字列とします。 なお、目的は、0979という名のファイルを作ることです。
- 締切済み
- C・C++・C#
- 文字列の動的確保とポインタ配列について
C言語についての質問です。 現在、キーボードから文字列を読み込みファイルに保存するプログラムを作成しています。 プログラムの条件は、以下の通りです。 1: キーボードから英数字(最長でMAX_LEN(1000)-1文字)を入力して文字列(文字配列)dataに格納後、画面に表示する。 2: 入力された文字列と同じ長さの文字列を格納する領域を動的に確保し、文字列dataをその領域に コピーする。なお、必要な文字配列の長さは文字列の長さ+1バイトである。 3: 文字列endが入力されるか、入力された文字列がNUM_STRING(10)個になるまで1～2の処理を繰り返す 4: 各文字列へのポインタを格納する(char *)型ポインタの配列str_p(サイズ:NUM_STRING)を定義して利用する。 5:1～2の処理が終了した後で、メモリに格納されたすべての文字列をファイルに出力する。ファイル名はoutput.txtとし、最初の行に文字列の個数を、次の行以降に入力された順番と「逆の順番」で文字 列を出力すること。 実行例 input ->st22 st22 input->st1 st1 end ファイルの中身 2 st1 st22 現在完成しているプログラムは以下の通りです。 #include<stdio.h> #include<string.h> #include <stdilb.h> #define NUM_STRING 10 #define MAX_LEN 1000 int main (void) { int n, i; char data[MAX_LEN] = {}; char *str_p[NUM_STRING]; FILE *fp; do { printf("input->"); scanf("%s", data); if (strcmp(data, "end") == 0) { break; } else { printf("%s\n", data); n++ 2の処理 } while(n <= NUM_STRING); if ((fp = fopen("output.txt", "w")) == NULL) { fprintf(stdout, "File open error\n"); } fprintf(ｆp, "%d\n", n); for (i = n-1; i>0; i--) fprintf(fp, "5s\n", str_p[i]); fclose (fp); return 0; } 特に動的確保のところがよく分かりません。 回答よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 配列にある文字と文字列との一致を調べたい
ＰＨＰについては素人同然で このような質問を失礼します。 $hensu に入っている文字と $myword の文字（配列）とを比較して、 一致、不一致の処理を行いたいと考えています。 $myword にはＮＧのワードを複数入れたいので $myword = explode(",", "ああ,いい,うう"); という処理をするつもりです。 ＮＧワードですので今後も増える可能性が ありますので。 このような形で処理する方法をお教えください。 何卒よろしくお願いします。
- ベストアンサー
- PHP
- 文字列の中の1文字を比較するには？
XP,Studio.NETでC++を書いています。 文字列の中の１文字を比較したいのですがどのようにしたらいいのかわかりません。 今以下のような文字列がstring[300]に入っているとします。 「\nは改行コードです。printf("");では"から"までの文字が画面に表示されます。」 このとき、１文字ずつを取り出し、文字を比較したいのですが (iを増加) if(string[i]=='\') flag=1; //処理→次にnが来る。 if(string[i]=='"') flag=2; //処理→文字はダブルコーテーション という処理をしたいのですが、 エラー：定数が多すぎます。 エラー：定数が2行目に続いています。 と出ます。どうしたらいいのでしょうか？ どなたか教えていただけると幸いです。
- ベストアンサー
- C・C++・C#
- 文字列
・文字列をキーボードから入力する関数を作成する。 書式：char *StrInp(char *pDefStr, int nLen); 引数：char *pDefStf; 初期文字列 int nLen; 入力可能文字数(1～79) 戻り値：正常ならば、入力した文字列の先頭ポインタ、エラー時はNULL。 処理：pDefStrに与えた文字列を初期値とする文字入力を行う。 nLenで指定した文字数まで入力可能とし、その範囲は1～79 までする。入力時の初期カーソル位置は与えた文字列の最後 になります。初期文字列が必要ない場合はヌル文字を与えます。 初期文字列を与えられた場合は、その文字列も更新可能とする。 ・入力の終了は「リターン」キーとする。 ・「BS」キーを押すと、カーソルの1文字前の文字前の文字を 消去する。 という、問いです。難しくてわかりません。どなたかたすけてください。
- ベストアンサー
- C・C++・C#
お礼
詳しいご説明ありがとうございます。ただ自分で実装するのは困難そうです。既に確立したアルゴリズムのようですし、どこかに既成のライブラリがありませんかね？このようなことをやりたい人はそれなりにいると思いますし、フリーのツールもありそうな感じなのですが。