基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

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

　C₁～C₁₀,C₂～C₁₁,…,C₉₀～C₉₉,C₉₁～C₁₀₀

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

　C₁～C₁₁,C₂～C₁₂,…,C₈₉～C₉₉,C₉₀～C₁₀₀

の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」になります。