(66.1) 一つの文字、たとえば「a」や「1」を「文字」と呼び、 文字が有限個並んだものを「文字列」という。 「hello, world」、「I」、 「3.141592」は文字列である。
(66.2) ブラウザやテキストエディタに表示されている文章の中から、 たとえば「print」という文字列を探したい、という場合がある。 これを「文字列の検索」、あるいは単に「検索」という。
(66.3) まず、テキストエディタ emacs を使って、 実際のソフトウェアでの検索を体験しよう。 いままでに作ったソートのプログラムのうちの一つを、emacs に読み込ませよう。 Ctrl+S を押すと検索が始まる。 画面左下に「I-search:」という文字列が現れる。 ここで、探したい文字列を打ってゆく。 たとえば「print」と打ってみよう。 途中で間違えたら、Ctrl+G を何回か押して取り消し、 最初からやり直しである。 探していた箇所が見つかれば、Enter を押すか、矢印キーを押すと、 そこからまたエディットが続けられる。 そうでなければ、Ctrl+S をまた押すと、 次の「print」にカーソルが移る。 Ctrl+S を押すことのくり返しで、 次々と「print」を見つけることができる。 このとき、「次の」というのは「それより後の」の意味だが、 Ctrl+S の代わりに Ctrl+R を使うと、 反対に「それより前の」を検索する。 次に同じ単語を検索したいときは、 Ctrl+S のあと文字列を打ち込まずにもう一度 Ctrl+S を押せばよいなど、いろいろ便利な機能があるが、 それらはすべて省略する。 ブラウザや、Windows の「メモ帳」にも検索機能があるが、 これらはメニューから選んで進んでゆけば理解できると思うので説明は省略する。 （「編集」メニューの中にあることがある。）
(66.4) Ｃ言語には、「char 型」という、一文字を格納できる変数の型があり、 文字列はその配列として扱うことができる。 文字や文字列を操作するための関数が豊富に用意されており、 それらを学習したうえで、 「一つの（一般には比較的長い）文字列の中から、 別の（一般には比較的短い）文字列を検索する」 という問題に取り組むことができるが、 文字や文字列に関する学習にはそれなりの時間がかかるので、 ここでは、文字を数に、文字列を配列に置き換えて、 いままでの知識で取り組める問題を考える。 この問題は、実は、文字列の検索と全く同じ問題である。
(67.1) 「数字列」ということばは普通は使わない。ここだけのことばである。
(67.2) 配列 a[ ] に、先頭から途中までは（0 以外の）一桁の自然数が格納されており、 その次の項には 0 が格納されているとする。 それよりあとの項には何がはいっているかわからない。 このとき、a[ ] を先頭から見ていって、最初に出会う 0 の直前までを、 ここでは「数字列 a[ ]」と呼ぶことにする。
(67.3) たとえば、a[0] が 9, a[1] が 1, a[2] が 3, a[3] が 0 だったとすると、 数字列 a[ ] は「913」である。 a[4] 以降に何がはいっていようと、無関係である。 （この例では、この配列は大きさが 4 以上ないといけない。そうでないと、 a[3] が範囲からはみ出してしまうからである。）
(67.4) a[0] が 0 なら、この数字列は「」、すなわち、空なる数字列である。
(68.1) いま、百桁程度の数字列 a[ ] と、二、三桁の数字列 p[ ] が与えられたとする。 このとき、a[ ] の中のどこに p[ ] が現れているかを調べるプログラムを書きたい。 （数字列を与える部分、およびそれを画面に表示する部分も、自分で書く必要がある。）
(68.2) int a[N+1]; と宣言するのは、長さ N の数字列まで格納できるようにするためである。 そのためには、最後の 0 を入れるところを考慮して、このように +1 が必要となる。 int p[M+1]; も同様。
#include <stdio.h>
#include <stdlib.h> /* srand() */
#include <time.h> /* time() */
#define N 120
#define M 3
int myrand(int lower, int upper);
void init(void);
void printa(void);
void printp(void);
int a[N+1]; /* +1 は最後の 0 のため */
int p[M+1];
main() {
int i, j;
init();
printp();
printa();
/* ここにプログラムの肝心な部分を書く */
}
/* lower から upper までの自然数に値をとる乱数を返す */
int myrand(int lower, int upper) {
/* 自分で考えて書く */
}
void init(void) {
int i, len; /* len は length の len */
{ /* この中カッコの中（乱数の種の設定）はわからなくてもよい */
unsigned seed = (unsigned)time(NULL); /* 現在時刻を取得して */
printf("乱数の種は %u です.\n", seed);
srand(seed); /* それを乱数の種に */
}
len = myrand(4*N/5, N); /* a[ ] の長さ */
/* ここで、乱数を利用し、a[0] から a[len-1] までを一桁の数で埋め、*/
/* a[len] には 0 を代入する。（それで a[ ] が数字列となる。） */
len = myrand(2*M/3, M); /* p[ ] の長さ */
/* ここで、乱数を利用し、p[0] から p[len-1] までを一桁の数で埋め、*/
/* p[len] には 0 を代入する。（それで p[ ] が数字列となる。） */
}
/* 数字列 a[ ] を出力し、最後に改行する */
void printa(void) {
/* 自分で考えて書く */
}
/* 数字列 p[ ] を出力し、最後に改行する */
void printp(void) {
/* 自分で考えて書く */
}
(68.3) このプログラムでは、ある自然数からある自然数までに値をとる乱数が何度も必要になるので、 まず、int myrand(int lower, int upper) を書こう。
(68.4) 関数 init() では、数字列の長さ len も乱数で決めている。 「len = myrand(4*N/5, N);」のように決めているが、 この右辺の小カッコの中の式に深い意味があるわけではない。適当である。 そのあとの二箇所を、コメントに従って、書け。
(68.5) 関数 printa() と関数 printp() を、コメントに従って、書け。 （実体はほとんど同一である。このように、数字列ごとに別の関数を書くのは、 実は無駄である。しかし、この授業ではこうしておく。）
(68.6) なお、printa(), printp() では、 配列 a[ ] や p[ ] の大きさを利用してはいけない。 数字列は 0 の手前で終わる、という事実だけを使うこと。 次に書く、main() の中の肝心な部分についても同様である。
(68.7) ここまで書いてコンパイル・実行すると、 数字列 p[ ] と a[ ]が次のように並んで表示されるはずである。
乱数の種は 1244788043 です. 52 858162662187116583221732245926279785621726596145434276287659346282443222761242653779286848541238163
(68.8) それから、main() の中の、肝心な部分を書け。 ここでは、数字列 a[ ] に現れる p[ ] をすべて探し出し、
乱数の種は 1244788252 です.
31
387211576631153486562123247268385875892263167176699791712417914481741864149644972821689797567684657
31
31
のように表示する。つまり、一致した箇所の真下に、p[ ] を出力する。
それには、次のようにすればよい。
(68.9) まず、int 型変数 i を一つずつ増やしながら、 p[ ] が a[i] からに現れているかどうか調べる。 現れていたら、そのときの i の値から決まるある個数だけスペースを出力し、 それから関数 printp() を呼ぶ。
(68.10) 正しく、すべて検索できたかどうかは、 出力結果を emacs のウィンドウに貼り付けて、 emacs の検索機能を用いて確認すること。(68.11) レポートはいつものようにメールで提出せよ。 件名は「kadai8」とせよ。 プログラムのほかに、 「見つからなかった場合」、「一つだけ見つかった場合」、「二つ以上見つかった場合」 の三つの出力結果を貼り付けること。
(68.12) 今回の出力結果は一行が長くなる。 Active! mail のメール作成ウィンドウに貼り付けると左右にはみ出るが、 気にしなくてよい。 うっかり変更しないよう注意して、そのまま送信せよ。
(68.13) ※ 提出すべきレポートでは、数字列は 1 から 9 までの数字の並んだものだが、 プログラムをほんの少しだけ改造して、 たとえば 1 から 3 までの数字だけが並ぶようにすれば、 p[ ] が a[ ] の中に見つかる確率が高まり、 多くの箇所で見つかるようになるであろう。これも試してみよ。