平成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 個がある。
- ア 2ⁿ－1
- イ n(n＋1)／2＋1
- ウ n(n－1)＋1
- エ n!＋1
解答・解説を見る
正解：イ
AI解説
長さnの文字列から取り出せる長さkの連続部分文字列は(n-k+1)個あり、k=1からk=nまで足し合わせると1+2+…+n＝n(n+1)/2となり、これに空文字列の1個を加えるとn(n+1)/2＋1となる。 ア: 2ⁿ－1は文字の並び順を保たない「部分列（subsequence）」の組合せ数に近い式であり、連続する部分文字列の数ではない。 イ: n(n+1)/2＋1が正しい。例のn=3では3×4/2+1=7となり、設問の例（7個）と一致する。これが正解。 ウ: n(n-1)＋1は例のn=3で3×2+1=7とたまたま一致して見えるが、一般のnでは正しい個数を与えない式である。 エ: n!＋1は順列の総数に近い式であり、部分文字列の個数を表す式ではない。 💡 連続部分文字列の総数は「長さ1からnまでの部分文字列数の和＋空文字列1個」＝(1+2+…+n)+1＝n(n+1)/2+1と導出できる。
出典：平成21年度 春期 応用情報技術者試験 午前 問4 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。