文字列の中から並びを探す｜擬似言語のトレース解説と練習問題

レベル：中級　／　タグ：for・while・文字・配列・探索・文字列処理

関数 find は、文字の配列 text の中で、文字の配列 pat と同じ並びが最初に現れる位置（先頭の要素番号）を返す。現れなければ 0 を返す。配列の要素番号は 1 から始まる。

プログラム

1	○整数型: find(文字型の配列: text, 文字型の配列: pat)
2	整数型: i, j
3	for (i を 1 から textの要素数－ patの要素数＋ 1 まで 1 ずつ増やす)
4	j ← 1
5	while (j ≦ patの要素数 and text[i ＋ j － 1] ＝ pat[j])
6	j ← j ＋ 1
7	endwhile
8	if (j > patの要素数)
9	return i
10	endif
11	endfor
12	return 0

何をしているか

i を「照合を始める位置」として 1 つずつずらしながら、その位置から pat と1文字ずつ比べます。j は「pat の何文字目を比べているか」です。全部一致したら i を返します。

トレースのコツ

表には i、j、比べている2文字（text[i ＋ j － 1] と pat[j]）を書きます。
外側の繰返しに入るたびに、j は 1 に戻ります。
while を抜けたあとの j を見れば、何文字目で違ったかが分かります。

よくある間違い

text[i ＋ j － 1] の － 1 を忘れる。j が 1 のとき、比べる相手は text[i] です。
条件式の評価回数を、文字が一致した回数と同じにしてしまう。一致しなかった回も数えます。
外側の繰返しの終わりを text の要素数にしてしまう。pat がはみ出さない位置までです。

例題：find({"a", "b", "b", "a", "b", "a"}, {"b", "a"}) を最後まで追う

上のプログラムを find({"a", "b", "b", "a", "b", "a"}, {"b", "a"}) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。

#	行	したこと	text	pat	i	j
1	2	宣言	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	未定義	未定義
2	3	繰返しの初期化	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	1	未定義
3	3	条件判定（真）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	1	未定義
4	4	代入	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	1	1
5	5	条件判定（偽）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	1	1
6	8	条件判定（偽）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	1	1
7	3	繰返しの更新	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	2	1
8	3	条件判定（真）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	2	1
9	4	代入	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	2	1
10	5	条件判定（真）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	2	1
11	6	代入	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	2	2
12	5	条件判定（偽）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	2	2
13	8	条件判定（偽）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	2	2
14	3	繰返しの更新	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	3	2
15	3	条件判定（真）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	3	2
16	4	代入	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	3	1
17	5	条件判定（真）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	3	1
18	6	代入	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	3	2
19	5	条件判定（真）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	3	2
20	6	代入	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	3	3
21	5	条件判定（偽）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	3	3
22	8	条件判定（真）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	3	3
23	9	戻る（3）	{"a", "b", "b", "a", "b", "a"}	{"b", "a"}	3	3

この例題で問われること

問　find({"a", "b", "b", "a", "b", "a"}, {"b", "a"}) を呼び出したときの戻り値はどれか。

答え　3

戻り値になる i は、1 → 2 → 3 と変わります。
9行目で返す時点の値 3 が答えです。

問　5行目の条件式が評価される回数はどれか。

答え　6

5行目の条件式は6回評価され、真が3回、偽が3回です。

問　6行目が実行される回数はどれか。

答え　3

6行目が実行されるのは、5行目の条件が真になったときだけです。
5行目の条件は6回評価され、真になるのは3回です。したがって 6行目は3回実行されます。

練習問題標準（10問）

本試験と同じくらいの量。レベル：中級

問題01　find({"b", "a", "a", "a", "b", "b"}, {"b", "b"})
問題02　find({"a", "a", "a", "b", "a", "b"}, {"a", "b"})
問題03　find({"b", "b", "b", "b", "a", "b"}, {"b", "a"})
問題04　find({"a", "a", "a", "a", "a", "b"}, {"a", "b"})
問題05　find({"b", "b", "a", "a", "b", "b"}, {"b", "a"})
問題06　find({"b", "a", "a", "a", "a", "b"}, {"a", "b"})
問題07　find({"a", "a", "b", "b", "a"}, {"b", "a"})
問題08　find({"b", "a", "a", "a", "b", "a"}, {"a", "b"})
問題09　find({"b", "b", "b", "a", "b"}, {"b", "a"})
問題10　find({"a", "a", "b", "b", "a", "b"}, {"b", "a"})

もっと解く（追加の20問）

問題11　find({"b", "b", "a", "b", "b"}, {"b", "a"})
問題12　find({"a", "b", "a", "b", "b"}, {"b", "b"})
問題13　find({"a", "a", "b", "b", "a"}, {"a", "b"})
問題14　find({"b", "a", "a", "b", "b", "b"}, {"b", "b"})
問題15　find({"a", "a", "a", "b", "b"}, {"a", "b"})
問題16　find({"a", "b", "a", "a", "b", "b"}, {"a", "a"})
問題17　find({"a", "a", "a", "b", "a"}, {"a", "b"})
問題18　find({"b", "a", "a", "b", "b"}, {"a", "b"})
問題19　find({"b", "b", "a", "a", "a", "a"}, {"b", "a"})
問題20　find({"b", "a", "b", "a", "a"}, {"a", "a"})
問題21　find({"b", "a", "b", "a", "a", "b"}, {"a", "a"})
問題22　find({"a", "b", "a", "a", "b"}, {"a", "a"})
問題23　find({"b", "a", "a", "a", "b"}, {"a", "b"})
問題24　find({"b", "a", "b", "b", "b", "b"}, {"b", "b"})
問題25　find({"b", "b", "a", "a", "a"}, {"b", "a"})
問題26　find({"a", "a", "b", "a", "a"}, {"a", "b"})
問題27　find({"a", "a", "b", "b", "b"}, {"a", "b"})
問題28　find({"b", "a", "b", "a", "a", "a"}, {"a", "a"})
問題29　find({"b", "b", "b", "a", "b", "b"}, {"b", "a"})
問題30　find({"a", "a", "b", "a", "b", "b"}, {"b", "b"})

ほかのアルゴリズム