問題プレビューID: 32edf661応用情報技術者試験 2009年(平成21年度)春期 午前

問 4
応用情報技術者試験 2009年(平成21年度)春期 午前

長さ n の文字列 c₁c₂…cₙ の中に,部分文字列は全部で幾つあるかを表す式はどれか。ここで,空文字列(長さ 0 の文字列)と c₁c₂…cₙ 自身も部分文字列とみなす。例えば,長さ 3 の文字列 c₁c₂c₃ の中に,部分文字列は c₁,c₂,c₃,c₁c₂,c₂c₃,c₁c₂c₃ 及び空文字列の 7 個がある。

解説

正解は「イ」です。

ここでの部分文字列は,元の文字列から連続して切り出せる文字列(連続部分文字列)を指します。長さ n の文字列では,開始位置と終了位置の組合せによって,空でない部分文字列が

n + (n−1) + … + 1 = n(n+1)/2 個

存在します。これに空文字列 1 個を加えると,全体では n(n+1)/2 + 1 個となります。

例えば n = 3 のとき,3×4/2 + 1 = 7 個となり,問題文の例と一致します。

  • ア: 2ⁿ−1 は「各部分文字列を含めるか含めないか」の組合せ(部分集合)の数であり,連続部分文字列の数ではありません。
  • ウ: n(n−1)+1 は n = 3 で 7 になりますが,n = 1 では 1 となり,空文字列を数え漏れます。
  • エ: 順列(n!)を基にした式は部分文字列の数とは関係ありません。

したがって,「イ」が正解です。

関連問題

本文が同じ・似ている問題を表示しています