Ninety Nine Percent Doomed
You count distinct substrings of one string by storing substring hashes in a hash set. Each hash is a single polynomial hash modulo . Any collision between two different substrings makes the count wrong.
With unordered pairs each colliding independently with probability about , the chance that at least one pair collides is approximately
Roughly what is ?
Sign in to answer questions and track your progress
Sign In