Title: Binary Jumbled Indexing: Suffix tree histogram Show Chinese title

Title: 二进制混洗索引：后缀树直方图

Abstract: Given a binary string $\omega$ over the alphabet $\{0, 1\}$, a vector $(a, b)$ is a Parikh vector if and only if a factor of $\omega$ contains exactly $a$ occurrences of $0$ and $b$ occurrences of $1$. Answering whether a vector is a Parikh vector of $\omega$ is known as the Binary Jumbled Indexing Problem (BJPMP) or the Histogram Indexing Problem. Most solutions to this problem rely on an $O(n)$ word-space index to answer queries in constant time, encoding the Parikh set of $\omega$, i.e., all its Parikh vectors. Cunha et al. (Combinatorial Pattern Matching, 2017) introduced an algorithm (JBM2017), which computes the index table in $O(n+\rho^2)$ time, where $\rho$ is the number of runs of identical digits in $\omega$, leading to $O(n^2)$ in the worst case. We prove that the average number of runs $\rho$ is $n/4$, confirming the quadratic behavior also in the average-case. We propose a new algorithm, SFTree, which uses a suffix tree to remove duplicate substrings. Although SFTree also has an average-case complexity of $\Theta(n^2)$ due to the fundamental reliance on run boundaries, it achieves practical improvements by minimizing memory access overhead through vectorization. The suffix tree further allows distinct substrings to be processed efficiently, reducing the effective cost of memory access. As a result, while both algorithms exhibit similar theoretical growth, SFTree significantly outperforms others in practice. Our analysis highlights both the theoretical and practical benefits of the SFTree approach, with potential extensions to other applications of suffix trees. Show Chinese abstract

Abstract: 给定一个二进制字符串 $\omega$ 在字母表 $\{0, 1\}$ 上，向量 $(a, b)$ 是一个 Parikh 向量当且仅当 $\omega$ 的一个因子包含恰好 $a$ 次出现 $0$ 和 $b$ 次出现 $1$。 回答一个向量是否是$\omega$的 Parikh 向量的问题被称为二元混洗索引问题（BJPMP）或直方图索引问题。 大多数解决该问题的方法依赖于一个$O(n)$字长的空间索引来以常数时间回答查询，编码$\omega$的 Parikh 集合，即它的所有 Parikh 向量。 Cunha 等人（《组合模式匹配》，2017）引入了一种算法（JBM2017），该算法在$O(n+\rho^2)$时间内计算索引表，其中$\rho$是$\omega$中相同数字的连续段数量，最坏情况下达到$O(n^2)$。 我们证明了平均的 $\rho$ 的数量为 $n/4$，从而也确认了平均情况下的二次行为。 我们提出了一种新的算法 SFTree，该算法使用后缀树来移除重复的子字符串。 尽管由于依赖于运行边界，SFTree 在平均情况下的复杂度也是 $\Theta(n^2)$，但它通过向量化减少了内存访问开销，从而实现了实际改进。 后缀树还允许高效处理不同的子字符串，降低了内存访问的有效成本。 因此，虽然两种算法在理论上表现出相似的增长趋势， 但在实践中，SFTree 显著优于其他算法。 我们的分析突出了 SFTree 方法在理论和实践上的优势，并展示了其扩展到后缀树其他应用的潜力。