An O(n log n) Algorithm for the Generalized Birthday Problem

In the combinatorial version of the generalized birthday problem, w 1's and n - w 0's are randomly arranged in either a line or a cycle; k sub m is defined to be the largest number of 1's appearing within any m consecutive positions. In the binomial version, each point is independently 1 with probability p and 0 with probability of 1 - p. Current algorithms for computing Pr (k sub m k) in the cases of practical interest where k and m are small, but n and w are large, require time exponential in both n and w.