必ず受かる情報処理技術者試験

問題4

ポケットスタディ 基本情報午後・要点整理―即効!7つの知識 (情報処理技術者試験)

長さn の文字列C1C2…Cnの中に、部分文字列は全部で幾つあるかを表す式はどれか。ここで、空文字列(長さ0の文字列)とC1C2…Cn自身も部分文字列とみなす。例えば、長さ3の文字列C1C2C3の中に、部分文字列はC1、C2、C3、C1C2、C2C3、C1C2C3及び空文字列の7個がある。

2n-1
n(n+1)/2+1
n(n-1)+1
n!+1

解答・解説を見る

解答:イ

【考え方1】

  1. n=1,n=2,n=3の場合の部分文字列の個数を考える。
  2. ア~エの選択肢にn=1,n=2,n=3を代入して演算結果が1と一致するのは(イ)n(n+1)/2+1である。

【考え方2】

  1. 長さ6の文字列c1c2c3c4c5c6をすべて数え上げると次のようになる。
    ※部分文字列なので、文字列中の文字を任意に取り出したり、順序を入れ替えたりする可能性はない。
    長さ6の部分文字列 c1c2c3c4c5c6 ⇒1個
    長さ5の部分文字列 c1c2c3c4c5,c2c3c4c5c6 ⇒2個
    長さ4の部分文字列 c1c2c3c4,c2c3c4c5,c3c4c5c6 ⇒3個
    長さ3の部分文字列 c1c2c3,c2c3c4,c3c4c5,c4c5c6 ⇒4個
    長さ2の部分文字列 c1c2,c2c3,c3c4,c4c5,c5c6 ⇒5個
    長さ1の部分文字列 c1,c2,c3,c4,c5,c6 ⇒6個
  2. 1より、長さnの文字列の長さ1~nの各部分文字列の個数は次のようになる。
    長さnの部分文字列 ・・・ 1個
    長さn-1の部分文字列 ・・・ 2個
    長さn-2の部分文字列 ・・・ 3個
       
    長さ3の部分文字列 ・・・ n-2個
    長さ2の部分文字列 ・・・ n-1個
    長さ1 の部分文字列 ・・・ n個
  3. 2よりその総数は、1+2+3+・・・(n-2)+(n-1)+nとなる。
  4. 等差数列の法則よりn(n+1)/2となる。
  5. 空文字列(長さ0の文字列)も部分文字列とするので、(イ)n(n+1)/2+1となる。
前の問題 次の問題

Copyrithg naruha