Given a string s over an alphabet a, b, a vector (x, y) is a Parikh vector if and only if a factor of s has exactly x a’s and y b’s. To answer whether or not a vector is a Parikh vector of a binary string is also known as the Binary Jumbled Pattern Matching Problem (BJPMP). Most solutions to this problem rely on a O(n) word space index to answer queries in constant time, which can encode the Parikh set, that is, all Parikh vectors of a binary string. We show that the BJPMP is equivalent to finding the prefix normal form (PNF) of the same string and the PNF, in turn, is equivalent to the O(n) bit space encode of the index. Cunha et al. (Combinatorial Pattern Matching, 2017) presented an algorithm that runs in \(O(n+\rho ^2)\) time to create the index table with the maximum of 1s, where \(\rho \) is the number of runs of 1s, reading from the start of each run to the end of each next run. This approach causes the algorithm to read repeated patterns for each occurrence. We develop an algorithm for constructing index tables using the essence of Ukkonen’s algorithm to create a suffix tree that purges repeated occurrences which, in practice, reduces the execution time—particularly in the cases where there are many repetitions of runs—and in addition builds the suffix tree which is a well-known data structure with many other applications. We provide the design and analysis of a new algorithm for constructing an index table from a string, with both theoretical and practical implications. Finally, we present a series of advantages found in our approach.