No.852
\(n = \abs{S}\) とする. \(S\) の部分文字列の数は \(\homoprod{n}{2}\) である.
\(S\) の部分文字列のうち a
が \(1\) つ以上含まれる数 \(c_a\) を考える. これは a
を \(1\) つも含まない部分文字列の数を全体から引けばいい. よって, a
の位置 (0-indexed) を \(a_1, a_2, \dots, a_{n_a}\) とすると,
となる. これをすべての文字で計算する.
平均の種類数は \((\sum c_i) / \homoprod{n}{2}\) で求められる.