探索

線形探索

　　線形探索は，配列やリストに保存されたデータに基づき，データの最初から一つずつ比較していく方法です．プログラムは簡単ですが，実行時間がかかります．ここでは，乱数によって 5,000,000 個のデータを生成し，その中から 50 個おきに取り出した（ 20 行目～ 23 行目）100,000 個の整数データを探索しています．

01	/****************************/
02	/* 線形探索                 */
03	/*      coded by Y.Suganuma */
04	/****************************/
05	#include <stdio.h>
06	#include <stdlib.h>
07	#include <time.h>
08	#include "MT.h"
09	
10	int main()
11	{
12				// 初期設定
13		int s[100000], n = 0;
14		int *data = new int [5000000];
15		init_genrand((unsigned)time(NULL));
16				// データの設定
17		clock_t tm1 = clock();
18		for (int i1 = 0; i1 < 5000000; i1++) {
19			data[i1] = genrand_int31();
20			if (i1%50 == 0 && n < 100000) {
21				s[n] = data[i1];
22				n++;
23			}
24		}
25		clock_t tm2 = clock();
26		printf("保存： %d ms\n", (int)(tm2-tm1));
27				// データの探索
28		for (int i1 = 0; i1 < n; i1++) {
29			int sw = 0;
30			for (int i2 = 0; i2 < 5000000; i2++) {
31				if (data[i2] == s[i1]) {
32					sw = 1;
33					break;
34				}
35			}
36			if (sw == 0) {
37				printf("***error*** データが見つからない！\n");
38				exit(1);
39			}
40		}
41		clock_t tm3 = clock();
42		printf("探索： %d ms\n", (int)(tm3-tm2));
43	
44		return 0;
45	}

（出力）

保存： 46 ms
探索： 182098 ms

二分探索（ Binary Search ）

　　二分探索は，ソートされた配列データに対して適用可能なアルゴリズムであり，その手順は以下に示すとおりです．線形探索の場合と同様，乱数によって 5,000,000 個の整数データを生成し，その中の 100,000 個のデータを探索しています．

配列をソートする（このプログラムでは，C++ 標準ライブラリ内のアルゴリズム一つである sort を利用）．以下の説明においては，昇順とするが，降順でも構わない．プログラムは，いずれの場合に対しても適用可能である．
探索範囲を配列全体とする．
探索範囲の右端の値が左端の値より大きい間，以下に示す処理を継続する．
- 中央の要素が目的の要素より小さければ，探索範囲を中央より後半の部分にする．
- 中央の要素が目的の要素より大きければ，探索範囲を中央より小さい部分にする．
中央にある要素と目的の要素を比較する．

　　参考のため，標準関数 bsearch（ 095 行目～ 103 行目），及び，C++ 標準ライブラリ内のアルゴリズム一つである binary_search（ 105 行目～ 113 行目）を利用した場合を併記しておきます．探索にかかる時間はほとんど同じです（場合によって，多少異なる）．

001	/****************************/
002	/* 二分探索                 */
003	/*      coded by Y.Suganuma */
004	/****************************/
005	#include <stdio.h>
006	#include <stdlib.h>
007	#include <time.h>
008	#include <algorithm>
009	#include "MT.h"
010	
011	using namespace std;
012	
013	/*************************/
014	/* データの比較（昇順）  */
015	/*      bsearch 用       */
016	/*************************/
017	int compare_n(const void *arg1, const void *arg2)
018	{
019		int *a1 = (int *)arg1;
020		int *a2 = (int *)arg2;
021		return *a1 - *a2;
022	}
023	
024	/**************************************/
025	/* 二分探索（ Binary Search ）        */
026	/*      key : 探索するキーデータ      */
027	/*      data : データ                 */
028	/*      n : データ数                  */
029	/*      return : 1 : 見つかった       */
030	/*               0 : 見つからなかった */
031	/**************************************/
032	bool search(int key, int *data, int n)
033	{
034		int sw = 0, left = 0, right = n-1, center;
035	
036		if (data[right] > data[left]) {
037			while (left < right) {
038				center = (left + right) / 2;
039				if (data[center] < key)
040					left = (center < n-1) ? center + 1 : center;
041				else
042					right = center;
043			}
044		}
045		else {
046			while (left < right) {
047				center = (left + right) / 2;
048				if (data[center] > key)
049					left = (center < n-1) ? center + 1 : center;
050				else
051					right = center;
052			}
053		}
054	
055		if (data[left] == key)
056			sw = 1;
057	
058		return sw;
059	}
060	
061	#define N 5000000
062	
063	int main()
064	{
065				// 初期設定
066		int s[100000], n = 0;
067		int *data = new int [N];
068		init_genrand((unsigned)time(NULL));
069				// データの設定
070		clock_t tm1 = clock();
071		for (int i1 = 0; i1 < N; i1++) {
072			data[i1] = genrand_int31();
073			if (i1%50 == 0 && n < 100000) {
074				s[n] = data[i1];
075				n++;
076			}
077		}
078		clock_t tm2 = clock();
079		printf("保存： %d ms\n", (int)(tm2-tm1));
080				// データのソート
081		sort(data, data+N);
082		clock_t tm3 = clock();
083		printf("sort： %d ms\n", (int)(tm3-tm2));
084				// データの探索
085		for (int i1 = 0; i1 < n; i1++) {
086			int sw = search(s[i1], data, N);
087			if (sw == 0) {
088				printf("***error*** データが見つからない！\n");
089				exit(1);
090			}
091		}
092		clock_t tm4 = clock();
093		printf("  探索： %d ms\n", (int)(tm4-tm3));
094				// データの探索（標準関数 bsearch の利用）
095		for (int i1 = 0; i1 < n; i1++) {
096			int *sw = (int *)bsearch(&s[i1], data, N, sizeof(int), compare_n);
097			if (sw == NULL) {
098				printf("***error*** データが見つからない！\n");
099				exit(1);
100			}
101		}
102		clock_t tm5 = clock();
103		printf("  探索(bsearch)： %d ms\n", (int)(tm5-tm4));
104				// データの探索（C++ 標準ライブラリ binary_search の利用）
105		for (int i1 = 0; i1 < n; i1++) {
106			bool sw = binary_search(data, data+N, s[i1]);
107			if (!sw) {
108				printf("***error*** データが見つからない！\n");
109				exit(1);
110			}
111		}
112		clock_t tm6 = clock();
113		printf("  探索(binary_search)： %d ms\n", (int)(tm6-tm5));
114	
115		return 0;
116	}

（出力）

保存： 30 ms
sort： 402 ms
  探索： 40 ms
  探索(bsearch)： 49 ms
  探索(binary_search)： 39 ms

ハッシュ法（ Hash ）

　　ディジタルデータの場合，どのようなデータでも数値（整数）とみなすことができますので，保存や探索時間だけのことを考えれば，大きなテーブル（配列）を用意しておき，数値としてみたデータが示す位置に保存する方法が最も効率的です．しかし，画像などであれば，天文学的なサイズの配列が必要になります．今まで扱ってきた整数データの場合でさえ，0 ～ 0x7fffffff ( 2,147,483,647 ) の値となりますので，配列のサイズを 2,147,483,648 以上にする必要があります．この問題を避ける一つの方法がハッシュ関数です．

　　ハッシュ関数とは，データをある区間にできるだけ一様に分布する整数に変換する関数です．ハッシュ法においては，データをハッシュ関数を利用して決められた範囲内の整数に変換し，テーブル上のその整数で指定された位置に保存します．しかし，異なるデータが同じ位置を占める場合（データの衝突）があるため，それを回避する方法が必要です．このプログラムでは，衝突が起こった場合，それらのデータを C++ 標準ライブラリ内の set クラスを使用して保存しています．線形探索の場合と同様，乱数によって 5,000,000 個の整数データを生成し，その中の 100,000 個のデータを探索しています（データは文字列に変換して記憶）．なお，ハッシュテーブルのサイズは，10,000,000 です．

001	/****************************/
002	/* ハッシュ法（ Hash ）     */
003	/*      coded by Y.Suganuma */
004	/****************************/
005	#include <stdio.h>
006	#include <stdlib.h>
007	#include <string.h>
008	#include <string>
009	#include <set>
010	#include <unordered_set>
011	#include <time.h>
012	#include "MT.h"
013	
014	using namespace std;
015	
016	int hit = 0;
017	
018	/***********************************/
019	/* クラス Hash（ハッシュテーブル） */
020	/***********************************/
021	class Hash {
022			int size;   // ハッシュテーブルの大きさ
023			set <string> *table;   // 衝突リスト
024	
025			/*******************/
026			/* ハッシュ関数    */
027			/*      s : 文字列 */
028			/*******************/
029			int hash(char *s)
030			{
031				unsigned int hash = 0;
032				int len = strlen(s);
033				for (int i1 = 0; i1 < len; i1++ ) {
034					hash = (hash << 4) + s[i1];   // 左に4ビットシフトし文字を加える
035					unsigned int g = hash & 0xf0000000;   // ビット毎のＡＮＤ
036					if (g != 0) {
037						hash ^= g >> 24;   // 排他的論理和
038						hash ^= g;
039					}
040				}
041	
042				return hash % size;
043			}
044	
045		public:
046	
047			/******************/
048			/* コンストラクタ */
049			/******************/
050			Hash(int sz)
051			{
052				size  = sz;
053				table = new set <string> [size];
054			}
055	
056			/***************************************/
057			/* データの追加                        */
058			/*      str : データ（文字列）         */
059			/*      return : =1 : 追加             */
060			/*               =0 : 同じデータが存在 */
061			/***************************************/
062			int add(char *str)
063			{
064				int k = hash(str);
065				if (!(table[k].empty()))
066					hit++;
067				pair<set<string>::iterator, bool> p = table[k].insert((string)str);
068				return p.second;
069			}
070	
071			/***********************************/
072			/* データの探索                    */
073			/*      str : データ（文字列）     */
074			/*      return : =1 : 見つかった   */
075			/*               =0 : 見つからない */
076			/***********************************/
077			int search(char *str)
078			{
079				int sw = 0;
080				int k  = hash(str);
081				set<string>::iterator it = table[k].find((string)str);
082				if (it != table[k].end())
083					sw = 1;
084				return sw;
085			}
086	};
087	
088	int main()
089	{
090				// 初期設定
091		int n = 0;
092		char s[100000][11];
093		Hash H(10000000);
094		init_genrand((unsigned)time(NULL));
095				// データの設定
096		printf("Hash\n");
097		clock_t tm1 = clock();
098		for (int i1 = 0; i1 < 5000000; i1++) {
099			int k = genrand_int31();
100			char st[11];
101			gcvt((double)k, 11, st);
102			st[strlen(st)-1] = '\0';   // 最後のピリオドが除かれる
103			int sw = H.add(st);
104			if (sw > 0) {
105				if (i1%50 == 0 && n < 100000) {
106					strcpy(s[n], st);
107					n++;
108				}
109			}
110			else
111				i1--;
112		}
113		clock_t tm2 = clock();
114		printf("   保存： %d ms， 衝突回数： %d\n", (int)(tm2-tm1), hit);
115				// データの探索
116		for (int i1 = 0; i1 < n; i1++) {
117			int sw = H.search(s[i1]);
118			if (sw == 0) {
119				printf("***error*** データが見つからない！\n");
120				exit(1);
121			}
122		}
123		clock_t tm3 = clock();
124		printf("   探索： %d ms\n", (int)(tm3-tm2));
125				// データの設定(string, unordered_set)
126		n = 0;
127		string* str = new string [100000];
128		printf("unordered_set(string)\n");
129		unordered_set<string> us;
130		for (int i1 = 0; i1 < 5000000; i1++) {
131			int k = genrand_int31();
132			char st[11];
133			gcvt((double)k, 11, st);
134			st[strlen(st)-1] = '\0';   // 最後のピリオドが除かれる
135			string sts(st);
136			pair<unordered_set<string>::iterator, bool> sw = us.insert(sts);
137			if (sw.second) {
138				if (i1%50 == 0 && n < 100000) {
139					str[n] = sts;
140					n++;
141				}
142			}
143			else
144				i1--;
145		}
146		clock_t tm4 = clock();
147		printf("   保存(string, unordered_set)： %d ms\n", (int)(tm4-tm3));
148				// データの探索(string, unordered_set)
149		for (int i1 = 0; i1 < n; i1++) {
150			unordered_set<string>::iterator it = us.find(str[i1]);
151			if (it == us.end()) {
152				printf("***error*** データが見つからない！\n");
153				exit(1);
154			}
155		}
156		clock_t tm5 = clock();
157		printf("   探索(string, unordered_set)： %d ms\n", (int)(tm5-tm4));
158				// データの設定(int, unordered_set)
159		n = 0;
160		int kk[100000];
161		printf("unordered_set(int)\n");
162		unordered_set<int> usi;
163		for (int i1 = 0; i1 < 5000000; i1++) {
164			int k = genrand_int31();
165			pair<unordered_set<int>::iterator, bool> sw = usi.insert(k);
166			if (sw.second) {
167				if (i1%50 == 0 && n < 100000) {
168					kk[n] = k;
169					n++;
170				}
171			}
172			else
173				i1--;
174		}
175		clock_t tm6 = clock();
176		printf("   保存(int, unordered_set)： %d ms\n", (int)(tm6-tm5));
177				// データの探索(int, unordered_set)
178		for (int i1 = 0; i1 < n; i1++) {
179			unordered_set<int>::iterator it = usi.find(kk[i1]);
180			if (it == usi.end()) {
181				printf("***error*** データが見つからない！\n");
182				exit(1);
183			}
184		}
185		clock_t tm7 = clock();
186		printf("   探索(int, unordered_set)： %d ms\n", (int)(tm7-tm6));
187	
188		return 0;
189	}

093 行目

　　Hash クラスの定義です．ハッシュテーブルのサイズを 10,000,000 としています．Hash クラスは，メンバー変数として，ハッシュテーブルの大きさを表す size とハッシュテーブル table （ string を要素とする set クラスのオブジェクトの配列）を持っています（ 022 行目～ 023 行目，050 行目～ 054 行目）．

099 行目～ 103 行目

　　乱数によって得られた整数を，標準関数 gcvt によって文字列に変換し，ハッシュテーブルに追加しています（ 103 行目）．

062 行目～ 069 行目

　　データをハッシュテーブルに追加するための Hash クラスのメンバー関数です．まず，064 行目において，ハッシュコード k を生成しています（具体的な処理は，029 行目～ 043 行目）．次に，table[k] に既にデータが存在するか否かをチェックし，存在した場合は衝突回数 hit を増加させています（ 066 行目）．最後に，table[k] が表す set にデータを追加しています（ 067 行目）．

077 行目～ 085 行目

　　ハッシュテーブル上のデータを検索するための Hash クラスのメンバー関数です．set クラスのメンバー関数 find を使用して，目的とするデータを探しています．

126 行目～ 157 行目

　　上と同様，文字列（ string ）データを unordered_set に保存し，探索を実行しています．

159 行目～ 186 行目

　　ここでは，int データを unordered_set に保存し，探索を実行しています．以下に示す出力結果に見るように，文字列に比較して，実行時間がかなり早くなっています．

（出力）　このプログラムを実行すると以下に示すような結果が得られます．ハッシュテーブルのサイズや衝突処理の方法によって，大きく異なってくると思います．

Hash
   保存： 8034 ms， 衝突回数： 1642507
   探索： 35 ms
unordered_set(string)
   保存(string, unordered_set)： 9292 ms
   探索(string, unordered_set)： 29 ms
unordered_set(int)
   保存(int, unordered_set)： 2256 ms
   探索(int, unordered_set)： 7 ms

文字列探索

　　プログラムは，文字列の探索を，C/C++ の標準関数を使用した場合，1 文字ずつ単純に比較した場合（単純な方法），BM 法を使用した場合，及び，C++ 標準ライブラリの string クラスを使用した場合を比較しています．ただし，私が使用している g++ のバージョンにおいては，string ヘッダを include すると，strstr が正しく動作しなくなってしまいましたので，string を使用する場合は異なるプログラムとして記述しています．いずれの場合においても，約 1,000,000 個の文字からなるテキストから，200 個の文字からなる 5,000 個の異なるパターンを検索しています．なお，5,000 個のパターンの半数には，テキストに存在しない文字が含まれています．

　　ここで，BM 法とは以下に示すような方法です．例として，テキスト "xyzcdxxxkbxyccbbxcacbbxx" を対象として，パターン文字列 "cacbb" を探索する場合について説明します．

パターンに現れる文字のずらし幅を決定します．つまり，パターンに現れる各文字に対して，その文字の右側に何文字存在するかの表を作成します．同じ文字が複数回現れる場合は，最も右側の文字だけを対象とします．この例の場合は，以下のようになります．

a b c

3 0 2
下に示すような位置において，パターンの右端の文字から対応するテキストの文字と比較していきます．
上の比較において，パターの右端の文字が異なっています．比較対象となるテキスト内の文字は 'd' ですが，この文字はパターンに含まれていません．そこで，以下に示すように 5 文字（パターンの文字列長）だけ右にずらします．
再びパターンの後ろから比較していくと，最初の文字は一致しますが，二番目の文字は異なっています．この場合も，比較対象となるテキスト内の文字 'k' がパターンに含まれていませんので，以下に示すように，再び，5 文字だけ右にずらします．
上の図に示した比較を行うと，先の場合のように 2 番目の文字が異なっています．しかし，先の場合とは異なり，比較対象となるテキスト内の文字 'c' はパターンに含まれています．そこで，先に作成したずらし幅の表に基づき，現在値（ k1 の値）を基準として，文字 'c' に対するずらし幅（ 2 ）だけ右にずらします（ k1 = k1 + 2 = 13 + 2 = 15 ）．
すると，上の図に示すように，4 番目の文字が異なり，かつ，比較対象となるテキスト内の文字 'c' がパターンに含まれています．ここで，先の場合と同じように，現在地を基準として右に 2 だけずらす（ k1 = k1 + 2 = 12 + 2 = 14 ）と，D で示した位置と一致してしまいます．このままでは，D と E を繰り返し，無限ループに入ってしまいます．そこで，現在の位置から決まるずらし幅（パターンの文字列長 - パターンの現在位置（ k2 の値） = 5 - 1 = 4 ）が，表から決まるずらし幅 2 より大きい場合は，現在の位置を基準にして，現在の位置から決まるずらし幅だけ右にずらします（ k1 = k1 + 4 = 12 + 4 = 16 ）．その結果，以下のような状態になります．
上の状態では，最初の文字が異なっており，かつ，比較対象となるテキスト内の文字 'x' がパターンに含まれていません．そのため，5 文字（パターンの文字列長）だけ右にずらします．
上の図からも明らかなように，この状態でパターンが見つかることになります．

a	b	c
3	0	2

001	/****************************/
002	/* 文字列探索               */
003	/*      coded by Y.Suganuma */
004	/****************************/
005	#include <stdio.h>
006	#include <string.h>
007	#include <time.h>
008	#include "MT.h"
009	
010	#define N 1000201
011	#define N1 5000
012	#define N2 200
013	
014	/****************************************************/
015	/* 単純な探索                                       */
016	/*      text : テキスト                             */
017	/*      ptn : 探索パターン                          */
018	/*      return : 発見位置のポインタ(失敗したらNULL) */
019	/****************************************************/
020	char *search_s(char *text, char *ptn)
021	{
022		char *s = NULL;
023		int len = (int)(strlen(text) - strlen(ptn));
024		for (int i1 = 0; i1 < len; i1++) {
025			int k  = i1;
026			int sw = 1;
027			for (int i2 = 0; i2 < (int)strlen(ptn); i2++) {
028				if (ptn[i2] != text[k]) {
029					sw = 0;
030					break;
031				}
032				else
033					k++;
034			}
035			if (sw > 0) {
036				s = &text[i1];
037				break;
038			}
039		}
040		return s;
041	}
042	
043	/****************************************************/
044	/* BM 法                                            */
045	/*      text : テキスト                             */
046	/*      ptn : 探索パターン                          */
047	/*      return : 発見位置のポインタ(失敗したらNULL) */
048	/****************************************************/
049	char *search_BM(char *text, char *ptn)
050	{
051		int len_t = (int)strlen(text);
052		int len_p = (int)strlen(ptn);
053				// ずらし幅テーブル
054		int step[255];
055		for (int i1 = 0; i1 < 255; i1++)
056			step[i1] = -1;
057		for (int i1 = len_p-1; i1 >= 0; i1--) {
058			if (step[(int)ptn[i1]] < 0)
059				step[(int)ptn[i1]] = len_p - 1 - i1;
060		}
061				// 実行
062		char *s = NULL;
063		int k   = len_p - 1;
064		while (k  < len_t) {
065			int k1 = k;
066			int k2 = len_p - 1;
067			int sw = 1;
068			while (k2 >= 0) {
069				if (ptn[k2] != text[k1]) {
070					if (step[(int)text[k1]] < 0)   // text[k1] がパターンに含まれない
071						k += len_p;
072					else {                         // text[k1] がパターンに含まれる
073						int k3 = step[(int)text[k1]];
074						int k4 = len_p - k2;
075						if (k3 > k4)
076							k = k1 + k3;
077						else
078							k = k1 + k4;
079					}
080					sw = 0;
081					break;
082				}
083				else {
084					k1--;
085					k2--;
086				}
087			}
088			if (sw > 0) {
089				s = &text[k-len_p+1];
090				break;
091			}
092		}
093		return s;
094	}
095	
096	/****************/
097	/* main program */
098	/****************/
099	int main()
100	{
101		clock_t tm1 = clock();
102		char **pattern = new char *[N1];
103		for (int i1 = 0; i1 < N1; i1++)
104			pattern[i1] = new char[N2+1];
105		char *text  = new char[N+1];
106	
107		init_genrand((unsigned)time(NULL));
108				// テキストと探索データの生成
109		int n = 0;
110		for (int i1 = 0; i1 < N; i1++) {
111			text[i1] = (char)(65 + 58 * genrand_real3());
112			if (n < N1 && i1 >= 2*N2 && (i1 % N2) == 0) {
113				int k = i1 - N2 - N2 / 2 - 1;
114				for (int i2 = 0; i2 < N2; i2++) {
115					pattern[n][i2] = text[k];
116					k++;
117				}
118				pattern[n][N2] = '\0';
119				if (n % 2 > 0)    // 存在しないデータの作成
120					pattern[n][N2/2] = '(';
121				n++;
122			}
123		}
124		text[N] = '\0';
125		clock_t tm2 = clock();
126		printf("***初期設定終了： %d ms***\n", (int)(tm2-tm1));
127				// 検索
128		printf("テキスト文字数 %d 探索パターン数 %d 探索パターン文字数 %d\n", N, n, N2);
129					// 標準関数 strstr
130		printf("標準関数 strstr\n");
131		tm1     = clock();
132		int hit = 0;
133		for (int i1 = 0; i1 < n; i1++) {
134			char *str = strstr(text, pattern[i1]);
135			if (str == NULL)
136				hit++;
137		}
138		tm2 = clock();
139		printf("   探索時間： %d ms　見つからなかったパターン数： %d\n", (int)(tm2-tm1), hit);
140					// 単純な方法
141		printf("単純な方法\n");
142		tm1 = clock();
143		hit = 0;
144		for (int i1 = 0; i1 < n; i1++) {
145			char *str = search_s(text, pattern[i1]);
146			if (str == NULL)
147				hit++;
148		}
149		tm2 = clock();
150		printf("   探索時間： %d ms　見つからなかったパターン数： %d\n", (int)(tm2-tm1), hit);
151					// BM 法
152		printf("BM 法\n");
153		tm1 = clock();
154		hit = 0;
155		for (int i1 = 0; i1 < n; i1++) {
156			char *str = search_BM(text, pattern[i1]);
157			if (str == NULL)
158				hit++;
159		}
160		tm2 = clock();
161		printf("   探索時間： %d ms　見つからなかったパターン数： %d\n", (int)(tm2-tm1), hit);
162	
163		return 0;
164	}

（出力）

***初期設定終了： 24 ms***
テキスト文字数 1000201 探索パターン数 5000 探索パターン文字数 200
標準関数 strstr
   探索時間： 3062 ms　見つからなかったパターン数： 2500
単純な方法
   探索時間： 231324 ms　見つからなかったパターン数： 2500
BM 法
   探索時間： 1374 ms　見つからなかったパターン数： 2500

C++ の string を使用した場合

01	/****************************/
02	/* 文字列探索(C++のstring)  */
03	/*      coded by Y.Suganuma */
04	/****************************/
05	#include <time.h>
06	#include <iostream>
07	#include <string>
08	#include "MT.h"
09	
10	#define N 1000201
11	#define N1 5000
12	#define N2 200
13	
14	using namespace std;
15	
16	/****************/
17	/* main program */
18	/****************/
19	int main()
20	{
21		clock_t tm1 = clock();
22		string pattern[N1];
23		string text = "";
24	
25		init_genrand((unsigned)time(NULL));
26				// テキストと探索データの生成
27		int n  = 0;
28		for (int i1 = 0; i1 < N; i1++) {
29			text += (char)(65 + 58 * genrand_real3());
30			if (n < N1 && i1 >= 2*N2 && (i1 % N2) == 0) {
31				int k      = i1 - N2 - N2 / 2 - 1;
32				pattern[n] = text.substr(k, N2);
33				if (n % 2 > 0)    // 存在しないデータの作成
34					pattern[n][N2/2] = '(';
35				n++;
36			}
37		}
38		clock_t tm2 = clock();
39		printf("***初期設定終了： %d ms***\n", (int)(tm2-tm1));
40				// 検索（ C++ string の find ）
41		printf("テキスト文字数 %d 探索パターン数 %d 探索パターン文字数 %d\n", N, n, N2);
42		printf("C++ string の find\n");
43		tm1     = clock();
44		int hit = 0;
45		for (int i1 = 0; i1 < n; i1++) {
46			int k = text.find(pattern[i1]);
47			if (k < 0)
48				hit++;
49		}
50		tm2 = clock();
51		printf("   探索時間： %d ms　見つからなかったパターン数： %d\n", (int)(tm2-tm1), hit);
52	
53		return 0;
54	}

（出力）

***初期設定終了： 62 ms***
テキスト文字数 1000201 探索パターン数 5000 探索パターン文字数 200
C++ string の find
   探索時間： 71004 ms　見つからなかったパターン数： 2500

二分探索木

［演習４］Ⅱ 章で示したアルゴリズに従って二分探索木を生成し（ただし，データは文字列でなく乱数によって生成した 5,000,000 個の整数データ），探索を行うプログラムを書き，線形探索，二分探索，ハッシュ法と実行時間を比較せよ．また，様々なケースに対して正しく動作することを確認すること．余裕があれば，ハッシュ法の衝突処理として，set クラスの代わりに，二分探索木を使用したプログラムを書き，先に示したプログラムと比較せよ．

Ⅳ．探索