Ninety Nine Percent Doomed

You count distinct substrings of one string by storing n=105n = 10^5 substring hashes in a hash set. Each hash is a single polynomial hash modulo m=109+9m = 10^9 + 9. Any collision between two different substrings makes the count wrong.

With (n2)\binom{n}{2} unordered pairs each colliding independently with probability about 1/m1/m, the chance that at least one pair collides is approximately

P≈1−e−(n2)/mP \approx 1 - e^{-\binom{n}{2}/m}

Roughly what is PP?

A

About 5 percent

B

About 99 percent

C

About 0.01 percent

D

About 10−910^{-9}