基本情報技術者平成18年秋期 午前問10

午前問10

長さ3の文字列C1C2C3の中には,長さ2以上の連続した部分文字列としてC1C2,C2C3,C1C2C3の三つがある。長さ100の文字列C1C2 … C100の中に,長さ10以上の連続した部分文字列が全部で幾つあるかを求める式はどれか。
  • 1+2+3+ … +88+89
  • 1+2+3+ … +89+90
  • 1+2+3+ … +90+91
  • 1+2+3+ … +98+99

分類

テクノロジ系 » 基礎理論 » 応用数学

正解

解説

まず長さ100の文字列の中に長さ10の部分文字列がいくつあるか考えると、

 C1〜C10,C2〜C11,…,C90〜C99,C91〜C100

の91種の部分文字列が存在することがわかります。続いて長さ11の部分文字列がいくつあるか考えると、

 C1〜C11,C2〜C12,…,C89〜C99,C90〜C100

の90種の部分文字列が存在することがわかります。つまり部分文字列の長さが1つ長くなるごとに存在する部分文字列の数は1つ減っていくという関係になっています。

長さ100の文字列の中に存在する最長の部分文字列は長さ100なので、文字列の長さを10から100まで増やしていった場合、部分文字列の数は
  • 長さ10の部分文字列→91種
  • 長さ11の部分文字列→90種
  • 長さ12の部分文字列→89種
  • -省略-
  • 長さ98の部分文字列→3種
  • 長さ99の部分文字列→2種
  • 長さ100の部分文字列→1種
となることがわかります。したがって長さ10以上の部分文字列の種類を求める式は「1+2+3+ … +90+91」になります。
© 2010-2020 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop