文字列探索

/****************************/
/* 文字列探索               */
/*      coded by Y.Suganuma */
/****************************/
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "MT.h"

#define N 1000201
#define N1 5000
#define N2 200

/****************************************************/
/* 単純な探索                                       */
/*      text : テキスト                             */
/*      ptn : 探索パターン                          */
/*      return : 発見位置のポインタ(失敗したらNULL) */
/****************************************************/
char *search_s(char *text, char *ptn)
{
	char *s = NULL;
	int len = (int)(strlen(text) - strlen(ptn));
	for (int i1 = 0; i1 < len; i1++) {
		int k  = i1;
		int sw = 1;
		for (int i2 = 0; i2 < (int)strlen(ptn); i2++) {
			if (ptn[i2] != text[k]) {
				sw = 0;
				break;
			}
			else
				k++;
		}
		if (sw > 0) {
			s = &text[i1];
			break;
		}
	}
	return s;
}

/****************************************************/
/* BM 法                                            */
/*      text : テキスト                             */
/*      ptn : 探索パターン                          */
/*      return : 発見位置のポインタ(失敗したらNULL) */
/****************************************************/
char *search_BM(char *text, char *ptn)
{
	int len_t = (int)strlen(text);
	int len_p = (int)strlen(ptn);
			// ずらし幅テーブル
	int step[255];
	for (int i1 = 0; i1 < 255; i1++)
		step[i1] = -1;
	for (int i1 = len_p-1; i1 >= 0; i1--) {
		if (step[(int)ptn[i1]] < 0)
			step[(int)ptn[i1]] = len_p - 1 - i1;
	}
			// 実行
	char *s = NULL;
	int k   = len_p - 1;
	while (k  < len_t) {
		int k1 = k;
		int k2 = len_p - 1;
		int sw = 1;
		while (k2 >= 0) {
			if (ptn[k2] != text[k1]) {
				if (step[(int)text[k1]] < 0)   // text[k1] がパターンに含まれない
					k += len_p;
				else {                         // text[k1] がパターンに含まれる
					int k3 = step[(int)text[k1]];
					int k4 = len_p - k2;
					if (k3 > k4)
						k = k1 + k3;
					else
						k = k1 + k4;
				}
				sw = 0;
				break;
			}
			else {
				k1--;
				k2--;
			}
		}
		if (sw > 0) {
			s = &text[k-len_p+1];
			break;
		}
	}
	return s;
}

/****************/
/* main program */
/****************/
int main()
{
	clock_t tm1 = clock();
	char **pattern = new char *[N1];
	for (int i1 = 0; i1 < N1; i1++)
		pattern[i1] = new char[N2+1];
	char *text  = new char[N+1];

	init_genrand((unsigned)time(NULL));
			// テキストと探索データの生成
	int n = 0;
	for (int i1 = 0; i1 < N; i1++) {
		text[i1] = (char)(65 + 58 * genrand_real3());
		if (n < N1 && i1 >= 2*N2 && (i1 % N2) == 0) {
			int k = i1 - N2 - N2 / 2 - 1;
			for (int i2 = 0; i2 < N2; i2++) {
				pattern[n][i2] = text[k];
				k++;
			}
			pattern[n][N2] = '\0';
			if (n % 2 > 0)    // 存在しないデータの作成
				pattern[n][N2/2] = '(';
			n++;
		}
	}
	text[N] = '\0';
	clock_t tm2 = clock();
	printf("***初期設定終了： %d ms***\n", (int)(tm2-tm1));
			// 検索
	printf("テキスト文字数 %d 探索パターン数 %d 探索パターン文字数 %d\n", N, n, N2);
				// 標準関数 strstr
	printf("標準関数 strstr\n");
	tm1 = clock();
	int hit     = 0;
	for (int i1 = 0; i1 < n; i1++) {
		char *str = strstr(text, pattern[i1]);
		if (str == NULL)
			hit++;
	}
	tm2 = clock();
	printf("   探索時間： %d ms　見つからなかったパターン数： %d\n", (int)(tm2-tm1), hit);
				// 単純な方法
	printf("単純な方法\n");
	tm1 = clock();
	hit = 0;
	for (int i1 = 0; i1 < n; i1++) {
		char *str = search_s(text, pattern[i1]);
		if (str == NULL)
			hit++;
	}
	tm2 = clock();
	printf("   探索時間： %d ms　見つからなかったパターン数： %d\n", (int)(tm2-tm1), hit);
				// BM 法
	printf("BM 法\n");
	tm1 = clock();
	hit = 0;
	for (int i1 = 0; i1 < n; i1++) {
		char *str = search_BM(text, pattern[i1]);
		if (str == NULL)
			hit++;
	}
	tm2 = clock();
	printf("   探索時間： %d ms　見つからなかったパターン数： %d\n", (int)(tm2-tm1), hit);

	return 0;
}