The binary jumbled indexing problem preprocesses a binary string so that one can quickly decide whether some substring has a given number of zeros and ones (a Parikh vector). This work analyses why the standard run-based construction is quadratic even on average -- proving that a random binary string has about n/4 runs -- and presents SFTree, a suffix-tree-based construction that removes duplicate substrings and, though still quadratic in theory, wins in practice by cutting memory-access cost through vectorization. Students learn how run structure controls the cost of jumbled indexing, how average-case analysis is carried out over random strings, and how a suffix tree turns repeated substructure into a practical speedup.
For a binary string over {0,1}, a pair (a,b) is a Parikh vector if some factor contains exactly a zeros and b ones; the Binary Jumbled Indexing Problem (BJIP) asks, after preprocessing the string, to…