文字列照合｜重ねて、ずらして、また重ねる【基本情報技術者試験科目B】

文字の並びの中から、目当ての並びを探す回です。A2-3 の探索と似ていますが、照らし合わせる相手が1文字ではなく、いくつかの並びである点が違います。

第2部　定番処理の型　全27回

A1-1トレース表の書き方 A1-2繰返しのトレース A1-3配列のトレース A2-1配列を全部見る A2-2最大・最小を見つける A2-3探す（線形探索）A2-4入れる・消す A2-52つの配列を突き合わせる A3-12次元配列の走査 A3-22次元配列の集計 A4-1文字列を1文字ずつA4-2文字列照合A5-1交換して並べる A5-2挿入ソート A6分割して並べるA7-12分探索A7-2ハッシュ表探索A8-1再帰とはA8-2再帰のトレースA9スタックとキューA10-1リストを読むA10-2リストの挿入と削除A11木構造A12木の巡回A13グラフA14AI・データを題材にしたプログラムA15ファイル処理

Table of contents

重ねて、ずらして、また重ねる
重ねはじめる位置は、どこまでか
違ったら、内側を抜ける
通しで見る
3 が返るまでを、1周ずつ追う
つまずきポイントまとめ
次に読む

重ねて、ずらして、また重ねる

登場するのは配列2本だけです。

この回で使う例

data探される側の並び　{"a", "b", "a", "b", "c", "a", "b", "c"}（8文字）

key探す並び　{"a", "b", "c"}（3文字）

data の中に "a" "b" "c" が続けて並んでいる場所を探し、その先頭が何番目かを答えます。この例なら 3番目です（data[3]＝"a"、data[4]＝"b"、data[5]＝"c"）。

やり方は素朴です。key を data の上に重ねて、ずらしながら試します。

重ねて、ずらして、また重ねる

data（8文字）の中から key（3文字）が続けて並んでいる場所を探す

i ＝ 1　1文字目から重ねる

3文字目で “a” と “c” が違う → ここはあきらめて、1つずらす

i ＝ 2　1つずらす

1文字目でいきなり “b” と “a” が違う → すぐずらす

i ＝ 3　もう1つずらす

3文字とも同じ → 先頭は3番目。ここで答えが決まる

外側が「どこに重ねるか」、内側が「重ねた中の何文字目か」

やること

key を data の先頭に重ねて、1文字ずつ照らし合わせる。1文字でも違ったら、1つずらして最初からやり直す。

だからくり返しは2重になります。外側が「どこに重ねるか」、内側が「重ねた中の何文字目か」です。

重ねはじめる位置は、どこまでか

外側のくり返しを最後まで回す必要はありません。key がはみ出す位置は、試すだけ無駄です。

重ねはじめる位置は、どこまでか

上限の式 ── dataの要素数－ keyの要素数＋ 1　（8 － 3 ＋ 1 ＝ 6）

i ＝ 6　ちょうど最後まで重なる

6・7・8 で終わる。これが最後に試せる位置

i ＝ 7　はみ出す

3文字目が data の外。試すだけ無駄なので、ここまで回さない

覚えるより、小さい数で数えて確かめるほうが早い

上限の式

dataの要素数－ keyの要素数＋ 1 まで。ちょうど最後まで重ねられる位置です。

ここもよく空欄になります。覚えるより、小さい数で確かめるほうが早いです。8文字の中から3文字を探すなら、6番目から重ねればちょうど 6・7・8 で終わります。

違ったら、内側を抜ける

1文字でも違ったら、その位置はもう見込みがありません。残りを照らし合わせても意味がないので、内側のくり返しを途中でやめます。

擬似言語には、そのための書き方があります。

αの行から始まる繰返し処理を終了する

読み方

α は、プログラムの中の for の行に付けられた目印です。「その for を抜ける」という意味で、外側は抜けません。

実際の出題にそのまま出ている

令和7年度の科目Bに、2つの文字型の配列を受け取って、同じ並びの先頭位置を全部返す search という関数が出ています。ここまでの3つが、そのまま使われています。

通しで見る

ここまでの3つを、1本にまとめます。最初に見つかった位置を返し、無ければ －1 を返す関数です。

当サイトで作った例です。令和7年度問4 の search は、見つかった位置を全部配列で返します。

○整数型: shougou(文字型の配列: data, 文字型の配列: key)
  整数型: i, j
  論理型: onaji

  for (i を 1 から (dataの要素数 － keyの要素数 ＋ 1) まで 1 ずつ増やす)
    onaji ← true
    for (j を 1 から keyの要素数 まで 1 ずつ増やす)  /* α */
      if (data[i ＋ j － 1] ≠ key[j])
        onaji ← false
        αの行から始まる繰返し処理を終了する
      endif
    endfor
    if (onaji ＝ true)
      return i
    endif
  endfor
  return －1

上から読む

```
○整数型: shougou(文字型の配列: data, 文字型の配列: key)
```
関数の見出し。探される側 data と、探す並び key を受け取り、先頭が何番目かを整数型で返します。
```
  整数型: i, j
  論理型: onaji
```
箱を3つ。i はどこに重ねるか、j は重ねた中の何文字目か。onaji は、途中で違わなかったかどうかを覚えておく論理型の箱です。
```
  for (i を 1 から (dataの要素数 － keyの要素数 ＋ 1) まで 1 ずつ増やす)
    onaji ← true
```
外側＝重ねる位置。上限が、さきほどの はみ出さない最後の位置です。1つずらすたびに onaji を true に戻してから照らし合わせます。
```
    for (j を 1 から keyの要素数 まで 1 ずつ増やす)  /* α */
      if (data[i ＋ j － 1] ≠ key[j])
```
内側＝重ねた中の何文字目か。比べる相手が data[i ＋ j － 1] です。α は、この for に付けた目印です。

        onaji ← false
        αの行から始まる繰返し処理を終了する
      endif
    endfor

違ったとき。印を false にして、内側だけ抜けます。外側は次の位置へ進みます。

```
    if (onaji ＝ true)
      return i
    endif
  endfor
  return －1
```
そこにあったか。内側を最後まで回りきって onaji が true のままなら、その位置 i を返します。どの位置でも見つからなければ －1 です。

3 が返るまでを、1周ずつ追う

shougou を1行ずつ動かす

当サイトオリジナルの例題

ループ開始前

配列

▲ いま読んでいる▲ いま書いた

いま計算していること

まだ計算していません

変数の状態

トレース表（進めると1行ずつ積み上がります）

shougou({"a", "b", "a", "b", "c", "a", "b", "c"}, {"a", "b", "c"}) を呼びます。外側の上限は 8 － 3 ＋ 1 ＝ 6 なので、i は 1 から 6 まで。

外側を1周ずつ

i ＝ 1。onaji を true に。
j＝1：data[1]＝"a"、key[1]＝"a"。同じ。
j＝2：data[2]＝"b"、key[2]＝"b"。同じ。
j＝3：data[3]＝"a"、key[3]＝"c"。違う→ onaji を false にして内側を抜ける。
i ＝ 2。j＝1 で data[2]＝"b" と key[1]＝"a" がいきなり違う→ すぐ抜ける。
i ＝ 3。j＝1：data[3]＝"a"。同じ。
j＝2：data[4]＝"b"。同じ。
j＝3：data[5]＝"c"。同じ→ 内側を最後まで回り切る。onaji は true のまま。

i ＝ 3 で if (onaji ＝ true) が成り立ち、return i で 3 が返ります。i ＝ 4 以降は回りません。

6番目も一致するが、見に行かない

data[6]〜data[8] も "a" "b" "c" ですが、この関数は最初の1つを返したところで終わりです。全部ほしいときは、return せずに別の配列へ足していきます（令和7年度問4 がその形）。

つまずきポイントまとめ

まちがえ方	正しい読み方
`data[i]` と `key[j]` を比べる	見るのは `data[i ＋ j － 1]`
`－1` を落とす	`j ＝ 1` のとき `i` そのものを見たい
外側を最後まで回す	`要素数－ keyの要素数＋ 1` まで
違っても内側を回し続ける	その位置は見込みなし。内側を抜ける
「繰返し処理を終了する」で外側も抜けると思う	目印の付いた `for` だけを抜ける

次に読む

A5-1	交換して並べる ─ バブルソートと選択ソート
A4-1	文字列を1文字ずつ見る ─ 文字数と i文字目の文字
G9-2	2重ループ ─ 内側と外側の回り方
目次	基本情報技術者試験科目B 攻略ガイド