科目Bの文字列照合問題の解き方｜照合する位置をずらして追う

text の (i ＋ j − 1) 文字目って、結局どこを見ているの？

科目Bの問題で、文章の中から決まった並びの文字を探すコードを見て、手が止まったことはありませんか？

ループが二重になっていて、添字の式も i と j が混ざっている。それだけで、読む気持ちがしぼんでしまう人も多いのではないでしょうか。

大丈夫です。文字列照合の問題は、探したい文字の並びを1文字ずつ横にずらしながら、重ねて比べているだけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、大量のログの中から特定のエラーコードを含む行を探す処理を書いたことがあり、文字列の終わりぎりぎりの位置を比べ忘れて、見つかるはずの行を取りこぼしたことがあります。

原因は、照合を始める位置の上限を1つ小さく書いていたことでした。このとき、短い文字列で位置を1つずつ紙に書き出したことで、ようやくずれに気づけました。

この記事では、文字列照合の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中でこうした問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

文字列照合の問題は何を聞いているのか¶

最初に、文字列照合とは何かを短く押さえておきましょう。名前は少し硬いですが、やっていることは、文章の中から目的の言葉を探すことです。

文字列照合とは、ある文字列の中に、別の短い文字列と同じ並びの部分があるかどうかを調べる処理のことです。探される長いほうを本文、探す短いほうをパターンと呼ぶことが多いです。

身近な例で考えてみましょう。ABABC という本文の中に、ABC という並びはあるでしょうか？

目で見れば、3文字目から始まる部分が ABC だとすぐに分かります。ところがコンピュータは、全体を一度に見渡すことができません。

そこで、パターンを本文の1文字目に重ねて比べ、合わなければ1文字右へずらしてまた比べる、という手順をくり返します。この素直な探し方を、力まかせ法と呼ぶこともあります。

科目Bで問われる形¶

試験の擬似言語で文字列照合が出るときは、探し方の考え方より、ループの範囲や添字の式が問われます。どんな形で聞かれやすいのかを、表に整理しました。

どの形でも、中心にあるのは、照合を始める位置と、比べる文字の位置の2つです。この2つを小さな例で確かめられれば、問われ方が変わっても同じ手順で解けます。

1文字を探す問題との違い¶

1文字だけを探す問題なら、ループは1つで足ります。本文を先頭から順に見て、目的の文字と等しい位置を返すだけです。

文字列照合では、パターンが複数の文字でできています。そのため、照合を始める位置を動かす外側のループと、パターンの中を1文字ずつ比べる内側のループの、2つが必要になります。

1文字ずつ取り出して調べる基本の読み方に不安がある場合は、こちらの記事で先に整理しておくと読みやすくなります。

【関連記事】科目Bの文字列問題の解き方｜1文字ずつ取り出す処理を追うコツ

まず目を付ける場所¶

文字列照合が何かつかめたら、次はコードのどこから読むかを決めます。文字列照合の問題では、目を付ける場所が3つあります。

ひとつ目は外側のループの範囲、ふたつ目は内側で比べている本文の位置の式、みっつ目は一致が決まったあとの戻り値です。この3か所が分かれば、ずれた選択肢をほぼ見抜けます。

照合を始める位置はどこまでか¶

最初に確かめたいのが、外側のループで i がどこまで動くかです。i は、パターンの1文字目を本文の何文字目に重ねるかを表しています。

本文が5文字で、パターンが3文字のときを考えてみましょう。パターンを本文の4文字目に重ねると、パターンの3文字目は本文の6文字目にはみ出してしまいます。

つまり、重ねられるのは3文字目までです。一般には、本文の文字数を n、パターンの文字数を m とすると、i の上限は n − m ＋ 1 になります。

なぜ ＋1 が付くのでしょうか？ 5 − 3 だけだと2になり、ちょうど右端にぴったり重なる3文字目の位置を比べ忘れてしまうからです。

本文の何文字目と比べているか¶

次に見るのが、内側のループで比べている本文の位置です。パターンの j 文字目は、本文の (i ＋ j − 1) 文字目に重なっています。

式だけを見ると難しく感じますが、j が1のときを考えれば納得できます。パターンの1文字目は本文の i 文字目に重ねたのだから、i ＋ 1 − 1 で i 文字目になる、というわけです。

j が1つ増えるごとに、本文の位置も1つ右へ進みます。−1 が付いているのは、添字が1から始まるためだと覚えておきましょう。

一致が決まったら何を返すか¶

最後に見るのが、パターンの最後の文字まで一致したあとの処理です。多くの問題では、見つかった位置として i を返します。

ここで返すのが i なのか j なのかは、選択肢でよく揺さぶられます。i は本文の中の位置、j はパターンの中の位置なので、見つかった場所を答えるなら i だと区別しておきましょう。

例題：本文の中からパターンを探す¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のプログラムは、本文 text の中にパターン pat が最初に現れる位置を返す関数です。見つからなければ −1 を返します。

○整数型: findPattern(文字列型: text, 文字列型: pat)
  整数型: n ← text の文字数
  整数型: m ← pat の文字数
  整数型: i, j
  論理型: matched
  for (i を 1 から n − m ＋ 1 まで 1 ずつ増やす)
    matched ← true
    j ← 1
    while ((j ≦ m) and matched)
      if (text の (i ＋ j − 1) 文字目 が pat の j 文字目 と等しくない)
        matched ← false
      else
        j ← j ＋ 1
      endif
    endwhile
    if (matched)
      return i
    endif
  endfor
  return −1

findPattern は、i を1つずつ右へずらしながら、パターンを本文に重ねて比べます。1文字でも合わなければ matched を false にして内側のループを抜け、次の位置へ進みます。

matched は、今の位置でここまで全部一致しているかを覚えておく論理型の変数です。こうした変数の読み方に慣れていない場合は、こちらの記事が参考になります。

【関連記事】擬似言語のフラグ変数（論理型）の使い方とは？見つかったかどうかを覚えておく処理を解説

では、findPattern("ABABC", "ABC") の戻り値は何になるでしょうか？

トレース表で照合の位置を追う¶

頭の中だけで二重のループを追うと、今どの位置に重ねているのかが分からなくなりがちです。そこで、比較1回ごとに、i と j、本文の位置、比べた2つの文字、その結果をトレース表に書きます。

ポイントは、本文の位置を i ＋ j − 1 で計算した値として、独立した列に書いておくことです。こうしておくと、添字の式を毎回頭の中で計算し直さずに済みます。

i が3のとき、j が3まで全部一致したので、j は4になって内側のループを抜けます。matched は true のままなので、return i で 3 を返します。

答えが合っているか不安なときは、本文を目で見て確かめましょう。ABABC の3文字目から3文字を取り出すと ABC で、表の結果と一致しています。

比べた回数も数えておくと、比較回数を聞かれたときに役立ちます。この例では、表の行数と同じ7回です。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

出現回数を数える形に変わったら¶

文字列照合には、最初の位置を返すのではなく、パターンが何回現れるかを数える形もあります。その場合は、return i の代わりに count ← count ＋ 1 と書き、ループを最後まで回します。

ここで注意したいのが、重なりのある出現です。AAAA という本文から AA を数えると、1文字目、2文字目、3文字目から始まる3か所が見つかります。

i は1つずつしか進まないので、重なっている部分も別々に数えられます。2回だと思い込まないように、位置を1つずつ表に書いて数えましょう。

比較の回数は最悪どれくらいになるか¶

力まかせの照合では、照合を始める位置がおよそ n か所あり、それぞれで最大 m 文字を比べます。つまり、比較の回数は最悪の場合、n と m の積に近い大きさになります。

ただし、実際には1文字目で外れることが多いので、平均するとずっと少なく済みます。設問が最悪の場合を聞いているのか、具体的な入力での回数を聞いているのかを読み分けましょう。

ループの形から処理の速さを見積もる考え方は、こちらの記事で詳しく扱っています。

【関連記事】科目Bの計算量問題の解き方｜ループの形からオーダーを判断する

間違いやすい選択肢の見分け方¶

文字列照合の問題では、ループの範囲や添字の式を少しだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題の findPattern("ABABC", "ABC") を使って、よくある誤りを表にまとめました。

正解の 3 に対して、2 や 4 のように近い数字が選択肢に並ぶのがこの種の問題の特徴です。計算結果だけを見て選ぶと、うっかり近い数字に飛びついてしまいます。

右端にぴったり重なる例で試す¶

上限で迷ったら、パターンが本文の最後にちょうど来る例を作ってみてください。例題の ABABC と ABC は、まさにその形になっています。

i の上限を n − m にすると、i は2までしか動きません。3文字目に重ねる位置を一度も比べないので、本当は見つかるのに −1 を返してしまいます。

一方で、上限を n にすると、パターンが本文からはみ出す位置まで比べに行きます。この例では1文字目で外れるので表面上は問題が起きませんが、本文が ABCAB なら、4文字目に重ねたときに本文の6文字目を見に行ってしまいます。

上限の誤りは、ふつうの入力では答えが合ってしまうことがあります。だからこそ、端にぴったり来る例を自分で作って試すのが確実です。

位置の式は j が1のときで確かめる¶

添字の式で迷ったら、j に1を入れてみましょう。正しい式なら、パターンの1文字目は本文の i 文字目に重なるはずです。

i ＋ j の式だと、j が1のときに本文の i ＋ 1 文字目を見てしまいます。最初の文字から1つずれているので、すぐに誤りだと分かります。

小さい値を入れて確かめる方法は、どんな添字の式にも使えます。選択肢ごとに1回試すだけで、ずれた式をほとんど落とせます。

実務でも境目の位置で不具合が出る¶

冒頭でお話ししたログの検索でも、ずれていたのは境目の1か所だけでした。真ん中にある文字列はきちんと見つかるのに、行の最後に書かれたエラーコードだけを取りこぼしていたのです。

テストで使っていたログは、たまたまエラーコードが行の途中にあるものばかりでした。端に来る例を1つ足したことで、ようやく不具合が表に出ました。

試験でも実務でも、境目は人がいちばん見落としやすい場所です。二重のループの範囲を見るときは、最初の位置と最後の位置を必ず確かめる習慣をつけておきましょう。

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。二重のループで位置がずれていく処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの比較で予想とずれたのかがすぐに分かります。

試すときは、まず正しい findPattern を動かして、i が3のときに return される様子を確かめてください。そのあと、上限を n − m に書き換えて、同じ入力で −1 が返ってくる様子を見ると、＋1 の大切さが体で分かります。

慣れてきたら、出現回数を数える形に書き換えたり、AAAA と AA のような重なりのある入力を試したりしてみましょう。i と j がどう動いているのかが、少しずつ見えてくるはずです。

二重のループそのものの読み方に不安が残る場合は、こちらの記事もあわせて読んでおくと安心です。

【関連記事】擬似言語の多重ループ（入れ子の繰返し）がわからない人へ｜二重forの読み方を解説

まずはGiji Academy の擬似言語シミュレーターで講座を選び、パターンが1文字ずつ右へずれていく様子を確かめてみてください。

まとめ¶

科目Bの文字列照合の問題は、特別なアルゴリズムの知識を問うものではありません。パターンを本文に重ね、合わなければ1文字ずらす、という手順を表に書いて追えば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、本文が5文字前後の短い例で十分です。何度か表を書くうちに、i ＋ j − 1 を見ただけで、パターンの j 文字目が本文のどこに重なっているのかが分かるようになります。

照合を始める位置の上限は n − m ＋ 1。迷ったら端にぴったり来る例で試す。 この2つを習慣にしておけば、文字列照合の問題にも自信を持って向き合えます。次に二重のループで文字を比べるコードに出会ったら、まずは i が1のときの重なり方を紙に書くところから始めてみてください。