平成21年度 春期 応用情報技術者試験 午前 問4
テクノロジ／基礎理論長さnの文字列c1c2…cnの中に，部分文字列は全部で幾つあるかを表す式はどれか。ここで，空文字列（長さ0の文字列）とc1c2…cn自身も部分文字列とみなす。例えば，長さ3の文字列c1c2c3の中に，部分文字列はc1，c2，c3，c1c2，c2c3，c1c2c3及び空文字列の7個がある。
出典：平成21年度 春期 応用情報技術者試験 午前 問4
- ア2ⁿ－1
- イn(n＋1)／2＋1
- ウn(n－1)＋1
- エn！＋1
正解：イ
解説
長さnの文字列の空でない連続部分文字列は，開始位置と終了位置の組合せで数えられ，n(n＋1)/2通りあります。これに空文字列の1個を加えると，全部でn(n＋1)/2＋1個になります。長さ3の例では3×4/2＋1＝7個となり，問題文の例と一致します。
選択肢ごとの解説
- ア誤り。2ⁿ－1は文字列から要素を選ぶ組合せ（連続でない部分列も含む）の数に近い式で，連続部分文字列の数ではありません。
- イ正しい。連続部分文字列はn(n＋1)/2通りあり，空文字列を加えるとn(n＋1)/2＋1個になります。
- ウ誤り。n(n－1)＋1は，例えばn＝3で7になりますが，n＝2で3となり実際の部分文字列数（空含め4個）と合いません。
- エ誤り。n！＋1は順列の数に基づく式で，部分文字列の数え方とは無関係です。