平成21年度 春期 応用情報技術者試験 午前 問4
長さ n の文字列 c₁c₂…cₙ の中に，部分文字列は全部で幾つあるかを表す式はどれか。ここで，空文字列（長さ0の文字列）と c₁c₂…cₙ 自身も部分文字列とみなす。例えば，長さ3の文字列 c₁c₂c₃ の中に，部分文字列は c₁，c₂，c₃，c₁c₂，c₂c₃，c₁c₂c₃ 及び空文字列の7個がある。
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：イ
-
ア: 2ⁿ−1
誤り。n＝3 のとき 2³−1＝7 となり例とは一致しますが，n＝2（c₁c₂）の場合は部分文字列が c₁，c₂，c₁c₂，空文字列の4個なのに対し，2²−1＝3 となり一致しません。2ⁿ は連続していない文字の組合せ（部分列）まで数える式です。 -
イ: n(n＋1)／2＋1
正しい。長さ k の部分文字列は n−k＋1 個あるので，長さ1〜n の合計は n＋(n−1)＋…＋1 ＝ n(n＋1)／2 個です。これに空文字列の1個を加えて n(n＋1)／2＋1 になります。n＝3 なら 6＋1＝7 で例と一致します。 -
ウ: n(n−1)＋1
誤り。n＝3 のとき 3×2＋1＝7 となり例とは一致しますが，n＝2 のときは 3 となり，正しい個数4と一致しません。 -
エ: n!＋1
誤り。n＝3 のとき 6＋1＝7 となり例とは一致しますが，n＝4 のときは 25 となり，正しい個数 4×5／2＋1＝11 と一致しません。
答え
イ: n(n＋1)／2＋1
出典：平成21年度 春期 応用情報技術者試験 午前 問4
