BM法を用いて、テキストファイルから指定の文字列を探す

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
クロック999

BM法を用いて、テキストファイルから指定の文字列を探す

#1

投稿記事 by クロック999 » 11年前

初めてこちらを利用させて頂きます。クロック999と申します。

BM法について学んでいるのですが、プログラムを組んでいて行き詰ってしまい、アドバイスを頂ければと思い投稿させて頂きました。

組んでいる課題は
・BM法を用いて、テキストファイルから検索ワードを探すプログラムを実現せよ。
・検索ワードが複数あった場合でも、1つが確認できれば2つめ以降の確認はなくてよい。
というものです。

私の考えでは、検索ワードのアスキーコードを利用し、スキップテーブルを作成する。
検索キーワードの文字列分だけ、テキストファイルの先頭から文字列をもってくる(text)。
検索ワードとtextを比較し、同じなら終了、違うならtxtをスキップテーブルに従い更新する、これを検索ワードが見つかるまで繰り返すという流れです。

以下が私が組んだプログラムです。

コード:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main(void)
{
    FILE *fp;
    char *fname = "sample.txt";

	char key[6];		//検索ワード	※今は暫定的に5文字
	int len;			//検索ワードの文字数

	char c;				//テキストから取り出す文字
	char txt[6];		//テキストから読み込んでおく文字列 ※今は暫定的に5文字

	int skip[128];		//スキップテーブル
	int i,k,n;

	n=5;	//※検索ワードの文字数
    
	/*検索ワードの入力*/
	printf("----\n");
	printf("検索ワード:");
	scanf("%s",key);
	printf("----\n");
	//printf("check1:検索ワード=%s\n",key);//確認

	/*検索ワードの文字数を調べる*/
	//len = strlen(key);
	//printf("check2;検索ワードの文字数=%d\n",len);//確認

	if((fp = fopen(fname,"r")) == NULL)
	{
        fprintf(stderr, "%sのファイルオープン失敗.\n", fname);
        exit(EXIT_FAILURE);
    }

	/*スキップテーブル作成*/

	for(i=0; i<128; i++)
		skip[i] = n;			//検索ワードの最後と無い文字は文字数分のスキップ

	for(i = 0; i < n-1; i++)
		skip[ key[i] ] = (n - i) -1;	//スキップテーブル作成

	//printf("check3:スキップテーブル\n");	//確認
	//for(i=0; i<128; i++)					//確認
	//	printf("skip[%d]:%d\n",i,skip[i]);	//確認

	/*文字列検索*/

	/*テキストから先頭のn文字ピックアップ,nはkeyの長さ*/
	for(i=0; i<n; i++) 
		txt[i] = fgetc(fp);
	txt[n]='\0';

	//printf("check4:ピックアップ %s\n",txt);//確認

	while((c = fgetc(fp)) != EOF)
	{
		/*keyとtxtの文字が同じかどうか見る*/
		k=n;
		while(txt[k] == key[k])
			k--;

		/*全て同じならk=0になっている*/
		if(k==0)
		{
			printf("テキスト中に検索ワードは含まれます\n");
			break;
		}
		/*一つでも違えばtxt[]を更新する*/
		else
		{			
			/*kの分押し出す*/
			for(i=0; i< skip[ key[k] ]; i++)
				txt[i] = txt[i+1];
			/*kの分読み込む*/
			txt[ skip[ key[k] ] ] = c;
			for(i = skip[ key[k] ] +1; i<n; i++)
			{
				if((c = fgetc(fp)) != EOF)
				{
					txt[i] = c;
				}
				else
				{
					break;
				}
			}
			printf("check5:更新した文字列 %s\n",txt);//確認
		}
	}
	printf("check0:終わり\n");

	return 0;
}
コメントアウトしている部分が多々あり、見づらいかと思いますが、後のチェックのために残してあります。

57行目以下の、比較と更新の作業がうまくいっていないようです。
check5で更新が正しく行われていないのが確認できています。
ですが、skip[key]を境目にして配列の押し出し、空いた部分にテキストファイルからもってくるという作業は出来ているはずだと思うのですが...(出来ていないから変な動作してるんですよね...)

あと文字の長さを勝手に決めているのは、nに値を読み取ってからint x[n];というような処理をしたいのですが、
使っているソフトが対応していないためできませんでした。
学校のパソコンだとできるので、最終的な手直しは学校で行います。

テキストファイルは
タイトル:sample.txt
内容:
My fellow citizens:
I stand here today humbled by the task before us, grateful for the trust you've bestowed, mindful of the sacrifices borne by our ancestors.
I thank President Bush for his service to our nation -- (applause) -- as well as the generosity and cooperation he has shown throughout this transition.

こちらを使用していました。

理想的な動作は、「テキスト中に検索ワードは含まれます」が、入力した検索ワードがあった場合ちゃんと標準出力されることです。
現状、テキストファイルの先頭の文字が検索ワードだった時にしか「テキスト中に検索ワードは含まれます」が出力されません。

長文乱文失礼しました。
ソースコードについてのアドバイスを、どうかよろしくお願いします。

“C言語何でも質問掲示板” へ戻る