長さ n の文字列 c₁c₂…cₙ の中に，部分文字列は全部で幾つあるかを表す式はどれか。ここで，空文字列（長さ 0 の文字列）と c₁c₂…cₙ 自身も部分文字列とみなす。例えば，長さ 3 の文字列 c₁c₂c₃ の中に，部分文字列は c₁，c₂，c₃，c₁c₂，c₂c₃，c₁c₂c₃ 及び空文字列の 7 個がある。