長さ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 の文字列の中に長さ0の文字列(空文字列)の数は、1個です。
長さn の文字列の中に長さ1の文字列の数は、n 個です。
長さn の文字列の中に長さ2の文字列の数は、n -1個です。
長さn の文字列の中に長さ3の文字列の数は、n -2個です。
…
長さn の文字列の中に長さn -1の文字列の数は、2個です。
長さn の文字列の中に長さn の文字列の数は、1個です。
したがって、部分文字列の個数は、
1+n +(n -1)+(n -2)+…+2+1
=1+(n +(n -1)+(n -2)+…+2+1)
=1+(n (n +1)/2)=n (n +1)/2+1
(イ)になります。
【キーワード】
・部分文字列
- 部分文字列
部分文字列は文字列から一部を切り出したものです。
部分文字列を求める処理は、各種検索機能で使われています。(検索エンジン、MS-Wordの検索など)
もっと、「部分文字列」について調べてみよう。
戻る
一覧へ
次へ