HOME»応用情報技術者平成21年春期»午前問4
応用情報技術者平成21年春期 午前問4
問4
長さnの文字列C1C2…Cnの中に，部分文字列は全部で幾つあるかを表す式はどれか。ここで，空文字列(長さ0の文字列)とC1C2…Cn自身も部分文字列とみなす。例えば，長さ3の文字列C1C2C3の中に，部分文字列はC1，C2，C3，C1C2，C2C3，C1C2C3及び空文字列の7個がある。
- 2n－1
- n(n＋1)／2＋1
- n(n－1)＋1
- n!＋1
分類
テクノロジ系 » 基礎理論 » 応用数学
正解
イ
解説
長さnの文字列には、n＋1個の境界があります。部分文字列はこの境界から始点と終点を選ぶことによって定義されるため、その種類はn＋1個の境界から2カ所を選ぶ組合せ数と同じくなります。
異なるN個のものからR個を選ぶ組合せ数は、NPRR!の公式で求めることができます。本問ではn＋1個から2個を選ぶため、(n＋1)×n2×1の式となり、これを整理するとn(n＋1)2となります。空文字も種類の1つに数えるとあるため、この式に1を加えた「イ」の式が正解となります。