応用情報技術者 2009年春期午前2 問04

問題文

長さ

n

の文字列

c_{1} c_{2} ... c_{n}

の中に、部分文字列は全部で幾つあるかを表す式はどれか。ここで、空文字列(長さ0の文字列)と

c_{1} c_{2} ... c_{n}

自身も部分文字列とみなす。例えば、長さ3の文字列

c_{1} c_{2} c_{3}

の中に、部分文字列は

c_{1}, c_{2}, c_{3},

c_1c_2c_3$及び空文字列の7個がある。

選択肢

ア：

2^{n} - 1

イ：

n (n + 1) /2 + 1

（正解）

ウ：

n (n - 1) + 1

エ：

n! + 1

長さ $n$ の文字列の部分文字列の数【午前2 解説】

要点まとめ

結論：長さ $n$ の文字列の部分文字列の総数は $n (n + 1) /2 + 1$ である。
根拠：部分文字列は連続した文字の列で、空文字列も含めるため、全ての開始位置と終了位置の組み合わせを数える。
差がつくポイント：部分文字列の定義に空文字列を含めるかどうか、また「部分文字列」と「部分集合」や「部分列」との違いを正確に理解することが重要。

正解の理由

部分文字列は文字列の中で連続した区間を指します。長さ

n

の文字列では、開始位置を

1

から

n

まで、終了位置を開始位置以上

n

まで選べます。
開始位置

i

に対して終了位置

j

は

i \leq j \leq n

なので、部分文字列の数は

\sum_{i = 1}^{n} (n - i + 1) = \frac{n ( n + 1 )}{2}

これに空文字列を加えるため、合計は

\frac{n ( n + 1 )}{2} + 1

となり、選択肢のイが正解です。

よくある誤解

部分文字列の数を

2^{n}

と勘違いしがちですが、これは部分集合の数であり、連続性を考慮していません。
また、部分列（非連続でもよい）と部分文字列（連続）を混同することも多いです。

解法ステップ

部分文字列の定義を確認する（連続した文字の列）。
開始位置 $i$ を $1$ から $n$ まで順に考える。
各開始位置に対して終了位置 $j$ は $i$ から $n$ まで選べる。
各区間の数を合計し、 $\sum_{i = 1}^{n} (n - i + 1) = \frac{n ( n + 1 )}{2}$ を求める。
空文字列を含めるために $+ 1$ する。
選択肢と照合し、 $\frac{n ( n + 1 )}{2} + 1$ （イ）を選ぶ。

選択肢別の誤答解説

ア: $2^{n} - 1$
部分集合の数から空集合を除いた数であり、部分文字列の数とは異なる。
イ: $n (n + 1) /2 + 1$
正解。部分文字列の数に空文字列を加えた式。
ウ: $n (n - 1) + 1$
部分文字列の数の計算として誤り。 $n (n - 1)$ は部分列や他の組み合わせ数と混同している可能性がある。
エ: $n! + 1$
順列の数であり、部分文字列の数とは無関係。

補足コラム

部分文字列は文字列処理やアルゴリズムで頻出の概念です。例えば、文字列の検索やパターンマッチング、動的計画法の問題で部分文字列の数や性質を理解していることが重要です。
また、部分列（subsequence）は連続性を問わず文字を選ぶため、数え方が異なります。部分列の数は

2^{n}

となります。

FAQ

Q: 部分文字列と部分列の違いは何ですか？
A: 部分文字列は連続した文字の列ですが、部分列は元の文字列の順序を保ちつつ連続でなくてもよい文字の列です。

Q: 空文字列を部分文字列に含める理由は？
A: 空文字列は長さ0の文字列として定義上含めることが多く、計算や理論上の整合性を保つためです。

関連キーワード: 部分文字列、文字列の長さ、組み合わせ、空文字列、連続性

← 前の問題へ次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2009年 春期 午前2 問04

問題文

選択肢

長さnの文字列の部分文字列の数【午前2 解説】