文字列の出現回数を数えるプログラム｜アルゴリズムとプログラミング問題を解くコツ

矢沢 久雄
2022-11-28 更新

この連載では、基本情報技術者試験で、多くの受験者が苦手意識を持っている科目 B 試験 アルゴリズムとプログラミング分野の「アルゴリズム穴埋め問題」に的を絞って、正解を見出すポイントを詳しく説明します。

苦手を克服するには、短いプログラムを何度も練習して、穴埋めに慣れることが重要です。

そのために、旧制度の午後試験のアルゴリズム過去問題の一部をアレンジした練習問題を作りました。とても短い問題ですので、気軽に取り組んでください。

練習問題

◯整数型: MatchCounter(文字型の配列: SourceText, 整数型: Textlen,
                     文字型の配列: Pattern, 整数型: Patlen)
  整数型: Counter, i, j, k
  論理型: Matchflg

  Counter ← 0
  i ← 0

  while (a)
    j ← i
    k ← 0
    Matchflg ← true

    while (k が Patlen より小さく かつ Matchflg が true)
      if ( SourceText[j] と Pattern[k] が等しい)
        j ← j + 1
        k ← k + 1
      else
        Matchflg ← false
      endif
    endwhile

    if (k が Patlen と等しい)
      Counter ← Counter + 1
    endif

    i ← i + 1
  endwhile

  return Counter

ポイント1: わかりやすい配列の絵を書いて問題のイメージをつかむ

「こういう配列の繰り返し処理の問題が、とにかく苦手なんです！」という人は、 わかりやすい具体例を想定して、配列の絵を書いてみる とよいでしょう。

問題に示されたプログラムは、汎用的なものであり、様々な配列を処理できますが、汎用的なままではイメージをつかめません。以下のように、具体的な配列の絵を書けば、イメージをつかめるはずです。

配列の絵を書いたことで、この問題は、絵に示された 10 文字の文字列 SourceText の中から、
[A][B][C]
という 3 文字の文字列 Pattern と一致する部分文字列の出現回数を数えるものとなり、その結果は 2 になります。

このように具体的な想定で問題に取り組めば、苦手意識が解消するでしょう。

ポイント2: 問題文にある説明や変数名から変数の役割を知る

プログラムは、登場人物がいてストーリーがある TV ドラマに似ています。プログラムでは、 変数が登場人物 に相当し、 処理の手順がストーリー に相当します。

登場人物の役割がわからなければ TV ドラマのストーリーがわからないように、変数の役割がわからなければプログラムの処理の手順はわかりません。

したがって、プログラムの処理を見る前に、変数の役割を知っておく 必要があります（プログラムを見ないと役割がわからない変数もありますので、可能な範囲で OK です）。

変数の役割は、問題文にある説明や、変数名などからわかります。

このプログラムに登場する変数と役割を以下にまとめて示します。

SourceText

探索対象の文字列（問題文の説明からわかる）

Textlen

SourceText の長さ（問題文の説明からわかる）

Pattern

探索する部分文字列（問題文の説明からわかる）

Patlen

Pattern の長さ（問題文の説明からわかる）

Counter

部分文字列の出現回数（問題文の手順の説明からわかる）

Matchflg

一致したことを表すフラグ（変数名からわかる）

i, j, k

配列の添字（プログラムの慣例としてわかる）

SourceText 、Textlen 、Pattern 、Patlen の役割は、問題文の説明からわかります。

Counter の役割は、問題文の手順の説明からわかります。
Matchflg の役割は、変数名（ Match = 一致、 flg = フラグ）からわかります。
i, j, k の役割は、プログラムの慣例としてわかります。配列の添字には、慣例として i を使い、さらに添字に関わる複数の変数が必要な場合は、アルファベットで i の次の j や、さらにその次の k などが使われます（ i, j, k が何を指す添字なのかは、プログラムを見たときにわかります）。

ポイント3: 問題文に示された手順とプログラムを対応付ける

試験問題に、処理の手順が示されていることがよくあります。この問題でも、 1. 2. 3. という番号を付けて、処理の手順が示されています。

この場合には、 それぞれの手順と照らし合わせながらプログラムを読んで行く とよいでしょう。

やみくもにプログラムを読むより、ずっとわかりやすいはずです。「この手順に該当するから、この穴埋めではこういう処理をするはずだ」と気付くこともあります。

以下は、処理の手順をプログラムに対応付けたものです。実際の試験では、このように丁寧な書き込みをしている時間はないと思いますので、メモ書き程度でやってください。

Counter ← 0
i ← 0

while (a)
  j ← i
  k ← 0
  Matchflg ← true

    while (k が Patlen より小さく かつ Matchflg が true)
      if ( SourceText[j] と Pattern[k] が等しい)
        j ← j + 1
        k ← k + 1
      else
        Matchflg ← false
      endif
    endwhile

    if (k が Patlen と等しい)
      Counter ← Counter + 1
    endif

    i ← i + 1
endwhile
return Counter1. 一致する部分文字列の出現回数を数える変数 Counter の値を 0 に初期化する。2. SourceText の比較開始位置を先頭から順に 1 文字ずつ後ろにずらしながら、(1.) その比較開始位置から始まる長さ Patlen の文字列と Pattern が一致するかどうかを調べ、(2.) 一致したら出現回数 Counter の値に 1 を加算する。3. Counter の値を返す。

穴埋めをやってみよう

それでは、穴埋めをやってみましょう。

基本情報技術者試験の問題は、すべて選択問題なので、解答群に示された選択肢をヒントにして考えてください（これも大事なポイントです）。もちろん、これまでに示した具体例の絵や、手順とプログラムの対応付けも、大いに活用してください。

aは、

2. SourceText の比較開始位置を先頭から順に 1 文字ずつ後ろにずらしながら

という手順に該当する部分であり、 擬似言語の表現から繰り返しの条件を指定するものであることがわかります。

a に関する解答群を見ると、この繰り返し処理の条件が、i, Textlen, Patlen という変数を使って示されています。さあ、どれでしょうか？

a に関する解答群

ア

i と Patlen の和が Textlen 以下

イ

i と Patlen の和が Textlen より小さい

ウ

i と Textlen の和が Patlen 以下

エ

i と Textlen の和が Patlen より小さい

ここで役立つのが具体例の絵です。

Textlen から Patlen を探索すると、最終的に以下の位置まで Patlen をずらすことになります。

i は、

i ← 0

で初期化してることから、比較の開始位置であり、配列の添字が 0 から始まるので、ここでは 7 です。

この具体例の絵から、 7 + 3 = 10 まで処理を行ってよいことがわかります。
これは、 7 + 3 の部分が 10 以下なら処理を繰り返してよいということです。

7 は i で、 3 は Patlen で、 10 は Textlen なので、この条件は、

i と Patlen の和が Textlen 以下

です。

したがって、選択肢アが正解です。できましたね！

解答ア

「習うより慣れろ」ということわざがあります。アルゴリズム穴埋め問題の克服に関しては、正にその通りでしょう。

この連載では、これからも短い練習問題を掲載していきますので、穴埋めに慣れることを目指してください。

正解を見出すポイントとして、同じことが示されることもあると思いますが、それは、多くの問題に共通したポイントがあるからです。

それでは、またお会いしましょう！

具体的な値を入れるとプログラムがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

具体例からヒントを掴む練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

プログラムを分割するコツがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

手順をヒントにトレースする練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

トレースのテクニックが身につく練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

2進数を掛け算するプログラム | アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

ヒープを配列で実現するプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

ルールに従って検査文字（チェックディジット）を求めるプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

配列のマッチング（突合せ）を行うプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

2進数の知識が必要なプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

矢沢 久雄

『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

• 「プログラムはなぜ動くのか」（日経BP）
• 「コンピュータはなぜ動くのか」（日経BP）
• 「出るとこだけ! 基本情報技術者」 (翔泳社)
• 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
• 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ）　など多数